kuangbin专题-最短路-POJ3268

原题链接

题意

有n个牧场，想要把所有牧场的牛赶到第x牧场中聚会，然后再回去，求里面母牛最大需要走的最短路程是多少
所有的路径都是单向路径

思路

对于floyd来说，这道题是会超时的
所以用了dijkstra
因为路径都是单向的，去和回来的路是不一样的
而dijkstra只能求出x牧场到其他牧场的最短路径，回去的道路是不能直接求出来的
所以得求出两次dijkstra

1. 第一次是求第x牧场到其他牧场的距离
2. 将所有的路径反转，例如a->b改成b->a
3. 路径反转后，再求一次dijkstra()，得出来的就是从其他牧场回到X牧场的最短路径
4. 接下了，只要把来回路径，求一个最大值，就是本题答案

注意

为了不写多个函数，所以我是直接用一个dijkstra函数，传入一个指针去计算的
传入的指针分别是从各个牧场到x牧场来回的最短路径
在初始化dist的时候，因为dist是指针类型，sizeof(dist)是等于4，不符合需要初始化的长度，而dist是用来指向distg和disth数组的，数组长度是N，int类型是4个字节，所以我们需要初始化的长度是4N，故需要memset(dist,0x3f,sizeof 4N);

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N=1010;

int n,m,x;
int g[N][N];
int distg[N];
int disth[N];
bool st[N];

void dijkstra(int *dist)
{
    int res=0;
    memset(dist,0x3f,sizeof 4*N);
    memset(st,0,sizeof st);
    dist[x]=0;
    for(int i=1;i<=n;i++){
        int k=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(k==-1||dist[k]>dist[j]))
                k=j;
        
        st[k]=true;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[k]+g[k][j]);
    }
    return ;
}
int main()
{
    int a,b,c;
    while(scanf("%d%d%d",&n,&m,&x)!=EOF){
        memset(g,0x3f,sizeof g);
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            g[a][b]=min(g[a][b],c);
        }
        dijkstra(distg);
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++) swap(g[i][j],g[j][i]);
        
        dijkstra(disth);
        int res=0;
        for(int i=1;i<=n;i++) res=max(res,distg[i]+disth[i]);
        printf("%d\n",res);
    }
    return 0;
}