#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1000+10;
int n,m,y,w[N][N],d[N][N],v[N];
void dijkstra()
{
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            d[i][j]=i==j?0:INF;
    memset(v,0,sizeof(v));
     for(i=1;i<=n;i++)//以2为起点；
     {
         int x,m=INF;
         for(j=1;j<=n;j++)
            if(!v[j]&&d[y][j]<=m)
            m=d[y][x=j];
            v[x]=1;
            for(j=1;j<=n;j++)
                d[y][j]=min(d[y][j],d[y][x]+w[x][j]);
     }
     memset(v,0,sizeof(v));
     for(i=1;i<=n;i++)//到2;
     {
         int x,m=INF;
         for(j=1;j<=n;j++)
            if(!v[j]&&d[j][y]<=m)
            m=d[x=j][y];
            v[x]=1;
            for(j=1;j<=n;j++)
                d[j][y]=min(d[j][y],d[x][y]+w[j][x]);
     }
     int maxx=0;
     for(i=1;i<=n;i++)
     {
         d[y][i]+=d[i][y]==INF?0:d[i][y];
         maxx=max(maxx,d[y][i]);
     }
//     for(i=1;i<=n;i++)
//        printf("2->%d %d\n",i,d[2][i]);
//     printf("***\n***\n");
//     for(i=1;i<=n;i++)
//        printf("%d->2 %d\n",i,d[i][2]);
     printf("%d\n",maxx);
}
int main()
{
    int i,j,a,b,c;
    scanf("%d%d%d",&n,&m,&y);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            w[i][j]=i==j?0:INF;
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        w[a][b]=c;
    }
//    printf("***\n***\n");
    dijkstra();
    return 0;
}

• Re:比较笨一点的方法，可以参考一下 (1688) sdufe202201140531 2024-03-27 14:48:57