其实还是从一个x点出发到所有点的最短路问题。来和回只需分别处理一下逆图和原图,两次SPFA就行了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<cctype>
#include<sstream>
using namespace std;
#define pii pair<int,int>
#define LL long long int
const int eps=1e-;
const int INF=;
const int maxn=+;
int n,m,x,a,b,t;
vector<int>vv1[maxn];
vector<int>vv2[maxn];
int t1[maxn][maxn],t2[maxn][maxn];
int d1[maxn],d2[maxn],ans=;
//以上1是原图的量,2是逆图的量
queue<int>q;
void spfa(int type)
{
if(type==)
{
q.push(x);
while(!q.empty())
{
int tt=q.front();
q.pop();
int st=vv1[tt].size();
for(int i=;i<st;i++)
{
int ti=vv1[tt][i];
if(d1[tt]+t1[tt][ti]<d1[ti])
{
d1[ti]=d1[tt]+t1[tt][ti];
q.push(ti);
}
}
}
}
else
{
q.push(x);
while(!q.empty())
{
int tt=q.front();
q.pop();
int st=vv2[tt].size();
for(int i=;i<st;i++)
{
int ti=vv2[tt][i];
if(d2[tt]+t2[tt][ti]<d2[ti])
{
d2[ti]=d2[tt]+t2[tt][ti];
q.push(ti);
}
}
}
}
}
int main()
{
//freopen("in8.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d%d%d",&n,&m,&x);
fill(d1,d1+maxn,INF);
fill(d2,d2+maxn,INF);
d1[x]=d2[x]=;
for(int i=;i<m;i++)
{
scanf("%d%d%d",&a,&b,&t);
t1[a][b]=t2[b][a]=t;
vv1[a].push_back(b);
vv2[b].push_back(a);
}
spfa();
spfa();
for(int i=;i<=n;i++)
{
ans=max(ans,d1[i]+d2[i]);
}
printf("%d\n",ans);
//fclose(stdin);
//fclose(stdout);
return ;
}