//Accepted 1124 KB 0 ms #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <algorithm> using namespace std; /** * This is a documentation comment block * 如果有一天你坚持不下去了,就想想你为什么走到这儿! * @authr songt */ ; ; const long long inf = 100000000000000LL; struct node { int u,v,c; node() { } node(int u,int v,int c):u(u),v(v),c(c) { } }p[imax_e],rp[imax_e]; int head[imax_n]; int next[imax_e]; int rhead[imax_n]; int rnext[imax_e]; int e; int re; long long dis[imax_n]; long long cost[imax_n]; bool vis[imax_n]; int n,m,x; void init() { e=; re=; memset(head,-,sizeof(head)); memset(next,-,sizeof(next)); memset(rhead,-,sizeof(rhead)); memset(rnext,-,sizeof(rnext)); } void addEdge(int u,int v,int c) { p[e]=node(u,v,c); next[e]=head[u]; head[u]=e++; } void raddEdge(int u,int v,int c) { rp[re]=node(u,v,c); rnext[re]=rhead[u]; rhead[u]=re++; } queue<int > q; int cnt[imax_n]; bool relax(int u,int v,int c) { if (dis[v]>dis[u]+c) { dis[v]=dis[u]+c; return true; } return false; } bool spfa(int src,int h[],int nt[],node p[]) { memset(cnt,,sizeof(cnt)); while (!q.empty()) q.pop(); memset(vis,,sizeof(vis)); q.push(src); vis[src]=true; ;i<=n;i++) dis[i]=inf; dis[src]=; while (!q.empty()) { int pre=q.front(); q.pop(); vis[pre]=false; ;i=nt[i]) { if (relax(pre,p[i].v,p[i].c) && !vis[p[i].v]) { if ((++cnt[p[i].v])>n) return false; vis[p[i].v]=true; q.push(p[i].v); } } } return true; } long long slove() { int u,v,c; init(); ;i<=m;i++) { scanf("%d%d%d",&u,&v,&c); addEdge(u,v,c); raddEdge(v,u,c); } ; spfa(x,head,next,p); ;i<=n;i++) { cost[i]=dis[i]; //printf("dis[%d]=%d\n",i,dis[i]); } spfa(x,rhead,rnext,rp); ;i<=n;i++) { //printf("cost[%d]=%d\n",i,dis[i]); if (cost[i]+dis[i]>ans) ans=cost[i]+dis[i]; } return ans; } int main() { while (scanf("%d%d%d",&n,&m,&x)!=EOF) { __int64 ans=slove(); printf("%I64d\n",ans); } ; }