最短路径练习2

P1364 医院设置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：

• 认真读题目就知道，这个题是医院建的点到各个点的路径之和最短，所以这个题是一个多源路径的题目，数据比较小，所以我直接选择用Floyed来做就可以，过程也比较简单，最后统计建在每个点的谁的总路径最小即可 。

代码如下：

#include 
#include 
#include 

P1576 最小花费 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：

• 借鉴的这位大佬的SPFA算法，利用队列进行松弛操作
• P1576 最小花费（最短路）_consult_的博客-CSDN博客
• 建立一张邻接表，然后利用队列和标记数组进行扫描，不断更新汇率最大的点（因为我们建立邻接表的时候其实边权值使用1-z，所以更新的是最一个点的最大边权值即最大汇率，才能狗保证最后输出的值越小）即可，如果有汇率更大的点就再压入队列中，直到队列中没有点时，即是扫描完了最后一个点，输入起点和终点，队列最先压进去的这个点为起点，扫描完成一遍后，输出记录的dis数组值，即为最大汇率，用100/最大汇率即可。

#include
#include
#include
#include
#include
//#define for(i,a,b)
using namespace std;
const int N = 3000;
const int M = 1000010;
int n, m, A, B, cnt;
double dis[N];
double head[N];
bool vis[N];
struct node
{
    int to;
    int next;
    double val;
}e[M];
void add(int x, int y, double z)
{
    cnt++;
    e[cnt].to = y;
    e[cnt].val = 1 - z;
    e[cnt].next = head[x];
    head[x] = cnt;
}
void spfa()
{ 
    queueq;
    q.push(A);
    dis[A] = 1;
    vis[A] = true;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        vis[p] = false;
        for (int i = head[p]; i; i = e[i].next)
        {
            int j = e[i].to;
            if (dis[j] < dis[p] * e[i].val) 
            {
                dis[j] = dis[p] * e[i].val;
                if (!vis[j])
                {
                    q.push(j);
                    vis[j] = true;
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(dis, 0, sizeof(dis));
    int x, y;
    double z;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        add(x, y, (double)z / 100);
        add(y, x, (double)z / 100);
    }
    cin >> A >> B;
    spfa();
    printf("%.8lf", 100 / dis[B]);
}

P1629 邮递员送信 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：

• 这个题是我之前写的，其实总体的思路是不难的，主要还是迪杰斯特拉，首先正向建图，用dis进行记录，统计一遍从原点1到各个点的最小路径，反向建图，再走一遍，统计每个点回去的最短路径，输出即可。 （注意反转矩阵，即反向操作的的时候，每次都需要初始化原点到每一个结点的路径值）

#include
#include 
#include 
using namespace std;
#define for(i,a,b)for(int i=a;i<=b;i++)
const int N = 2000;
int mp[N][N], dis[N];
const int INF = 0x3f3f3f3f;
void init(int n);
void dijkstra(int n);
void over(int n);
void lujing(int n);
int main()
{
    int n, m, x, y, w;
    int sum;
    cin >> n >> m;
    init(n);
    for (i,1,m)
    {
        cin >> x >> y >> w;
        mp[x][y] = min(mp[x][y], w);
    }
    lujing(n);
    dijkstra(n);
    for (i,1,n)
    {
        sum += dis[i];
    }
    over(n);
    lujing(n);
    dijkstra(n);
    for (i,1,n)
    {
        sum += dis[i];
    }
    cout << sum << endl;
    return 0;
}
void init(int n)//邻接矩阵初始化
{
    for (i,1,n)
    {
        for (j,1,n)
        {
            if (i != j)
                mp[i][j] = INF;
        }
    }
}
//dijkstra模板
void dijkstra(int n)
{
    bool vis[1010] = { 0 };
    vis[1] = 1;
    for (i,1,n-1)
    {
        int min = INF; 
        int index;
        for (j,1,n)
        {
            if (!vis[j] && min > dis[j])
            {
                min = dis[j];
                index = j;
            }
        }
        vis[index] = 1;
        for (j,1,n)
        {
            if (!vis[j] && mp[index][j] + dis[index] < dis[j])
            {
                dis[j] = mp[index][j] + dis[index];
            }
        }
    }
}
void over(int n)
{
    for (i,1,n)
    {
        for (j,i+1,n)
        {
            int temp = 0;
            temp = mp[i][j];
            mp[i][j] = mp[j][i];
            mp[j][i] = temp;
        }
    }
}
void lujing(int n) {
    for (i,1,n) {
        dis[i] = mp[1][i];
    }
}