每天进步一点点，今日dijkstra算法（队优化）

程序员文章站 2024-02-24 17:47:34

...

D - Silver Cow Party

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1…N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires T_i (1 ≤ T_i ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow’s return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively:
N, M, and X

Lines 2…
M+1: Line
i+1 describes road
i with three space-separated integers:
A_i,
B_i, and
T_i. The described road runs from farm
A_i to farm
B_i, requiring
T_i time units to traverse.

Output

Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

Sample Output

Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

大意是，有n个农场， n头奶牛要去编号为x的农场开party，但是农场之间是单向的，问在所有奶牛去x并返回原农场的最短路中，最长的是哪个（求最短路中最大的那个）
以前一直用的spfa，对dijkstra只是有所接触，但没写过，借这个题正好了解一下。
奶牛去x的最短路很好求，但奶牛回来的最短路比较难搞，如果直接暴力的话，应该会超时，百度了一波，发现有个方法，就是把这个矩阵转置，即MAP[i][j]=MAP[j][i],这样就变成了和奶牛去x时一样，求从各个点到x的最短路，由于是单向的，两次所得结果是不一样的，这样两次dijkstra后跑一个for 将第一次和第二次的最短路对应相加，找出其中的最大值，即是结果

#include <map>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1010;
int MAP[maxn][maxn],n;
int way[maxn], dis[maxn];
struct node
{
    int data, d;
    friend bool operator < (node a, node b)//优先队列的重载，应该没错吧，之前看他们的是有&符号，也不知道是什么鬼，但是编译器没有报错，应该是对的
    {
        return a.data > b.data;//stl库中涉及到排序都是按小于号排的，这里就是把小于号重载为大于号，所以这里是 >
    }
};
void dijkstra(int x)
{
    node temp, tem;
    memset(dis, INF, sizeof(dis));
    dis[x]=0;
    priority_queue<node> que;
    temp.data=dis[x];
    temp.d=x;
    que.push(temp);
    while(!que.empty())
    {
        temp=que.top();
        que.pop();
        if(dis[temp.d]<temp.data) continue;
        for(int j=1; j<=n; j++)
        {
            if(dis[j]>temp.data+MAP[temp.d][j])
            {
                dis[j]=temp.data+MAP[temp.d][j];
                tem=(node){dis[j], j};
                que.push(tem);
            }
        }
    }
}
int main()
{
    int m,x;
    while(cin>>n>>m>>x)
    {
        memset(MAP, INF, sizeof(MAP));
        for(int i=1; i<=n; ++i)
        {
            MAP[i][i]=0;
        }
        for(int i=0; i<m; i++)
        {
            int a, b, t;
            cin>>a>>b>>t;
            if(t<MAP[a][b])
                MAP[a][b]=t;
        }
        dijkstra(x);
        for(int i=1; i<=n; ++i)
        {
//            cout<<dis[i]<<endl;
            way[i]=dis[i];
        }
        int ans=0;
        for(int i=1; i<=n; ++i) //置换矩阵的值，也就是交换MAP[i][j]与MAP[j][i]的值
        {
            for(int j=i+1; j<=n; ++j)
            {
                int cnt;
                cnt=MAP[j][i];
                MAP[j][i]=MAP[i][j];
                MAP[i][j]=cnt;
            }
        }
//        cout<<"*****************************"<<endl;
        dijkstra(x);
        for(int i=1; i<=n; ++i)
        {
//            cout<<dis[i]<<endl;
            if(i!=x)
                ans=max(ans,way[i]+dis[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}
//这些都不重要，重要的是我要通过这道题掌握dijkstra算法。。。以及其队优化；