这道题用djstra方法做，当然也可以用贝尔曼做，开始做的时候被2000ms给骗了，一直TLE后来想想应该只是JAVA 2000ms，c++依然是1s。
现附上TLE的代码，粗略估算应该是10^9，超时了(O(N^3).....
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f
using namespace std;
const int maxn=1000+100;
int v[maxn],d[maxn],w[maxn][maxn],n,road,tar,from,to,cost,a[maxn],b[maxn],froms,maxs;int dj(int original)
{memset(v,0,sizeof(v));for(int i=1;i<=n;i++)d[i]=(i==original? 0:INF);for(int i=1;i<=n;i++){int x,m=INF;for(int y=1;y<=n;y++)if(!v[y]&&d[y]<=m) m=d[x=y];v[x]=1;for(int y=1;y<=n;y++) {d[y]=min(d[y],d[x]+w[x][y]);/*printf("%d:%d\n",y,d[y]);*/}}return d[tar]+d[froms];
}int main()
{scanf("%d%d%d",&n,&road,&tar);memset(w,INF,sizeof(w));maxs=0;while(road--){scanf("%d%d%d",&from,&to,&cost);w[from][to]=cost;}for(froms=1;froms<=n;froms++)if(froms!=tar)maxs=max(dj(froms)+dj(tar),maxs);//sort(maxs+1,maxs+1+n);printf("%d\n",maxs);// dj(tar);return 0;
}
后来看到别人的代码后恍然大悟，直接把整个图反过来求回家的路线就可以了，以下为AC代码
#include<cstdio>#include<iostream>#include<cstring>#include<cmath>using namespace std;#define INF 500000int sum[1050];int map[1050][1050];int dis[1050],mark[1050];int x,n,i,j;void d(){int min,k;memset(dis,0,sizeof(dis));memset(mark,0,sizeof(mark));for(i=1;i<=n;i++){dis[i]=map[x][i];}dis[x]=0;mark[x]=1;for(i=2;i<=n;i++){min=INF;for(j=1;j<=n;j++){if(!mark[j]&&min>dis[j]){k=j;min=dis[j];}}mark[k]=1;sum[k]+=min;for(j=1;j<=n;j++){if(!mark[j]&&map[k][j]+dis[k]<dis[j]){dis[j]=map[k][j]+dis[k];}}}}void up(){int t;for(i=1;i<=n;i++){for(j=1;j<=i;j++){t=map[i][j];map[i][j]=map[j][i];map[j][i]=t;}}}int main(){int m,le,max;while(scanf("%d %d %d",&n,&m,&x)!=EOF){max=0;memset(sum,0,sizeof(sum));memset(map,INF,sizeof(map));while(m--){scanf("%d %d %d",&i,&j,&le);map[i][j]=le;}d();up();d();for(i=1;i<=n;i++){if(max<sum[i])max=sum[i];}cout<<max<<endl;}return 0;}