1 //Accepted    1124 KB    0 ms  2 #include <cstdio>  3 #include <cstring>  4 #include <iostream>  5 #include <queue>  6 #include <cmath>  7 #include <algorithm>  8 using namespace std;  9 /** 10   * This is a documentation comment block 11   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 12   * @authr songt 13   */ 14 const int imax_n = 1005; 15 const int imax_e = 100005; 16 const long long inf = 100000000000000LL; 17 struct node 18 { 19     int u,v,c; 20     node() 21     { 22  23     } 24     node(int u,int v,int c):u(u),v(v),c(c) 25     { 26  27     } 28 }p[imax_e],rp[imax_e]; 29 int head[imax_n]; 30 int next[imax_e]; 31 int rhead[imax_n]; 32 int rnext[imax_e]; 33 int e; 34 int re; 35 long long dis[imax_n]; 36 long long cost[imax_n]; 37 bool vis[imax_n]; 38 int n,m,x; 39 void init() 40 { 41     e=0; 42     re=0; 43     memset(head,-1,sizeof(head)); 44     memset(next,-1,sizeof(next)); 45     memset(rhead,-1,sizeof(rhead)); 46     memset(rnext,-1,sizeof(rnext)); 47 } 48 void addEdge(int u,int v,int c) 49 { 50     p[e]=node(u,v,c); 51     next[e]=head[u]; 52     head[u]=e++; 53 } 54 void raddEdge(int u,int v,int c) 55 { 56     rp[re]=node(u,v,c); 57     rnext[re]=rhead[u]; 58     rhead[u]=re++; 59 } 60 queue<int > q; 61 int cnt[imax_n]; 62 bool relax(int u,int v,int c) 63 { 64     if (dis[v]>dis[u]+c) 65     { 66         dis[v]=dis[u]+c; 67         return true; 68     } 69     return false; 70 } 71 bool spfa(int src,int h[],int nt[],node p[]) 72 { 73     memset(cnt,0,sizeof(cnt)); 74     while (!q.empty()) q.pop(); 75     memset(vis,0,sizeof(vis)); 76     q.push(src); 77     vis[src]=true; 78     for (int i=1;i<=n;i++) 79     dis[i]=inf; 80     dis[src]=0; 81     while (!q.empty()) 82     { 83         int pre=q.front(); 84         q.pop(); 85         vis[pre]=false; 86         for (int i=h[pre];i+1;i=nt[i]) 87         { 88             if (relax(pre,p[i].v,p[i].c) && !vis[p[i].v]) 89             { 90                 if ((++cnt[p[i].v])>n) return false; 91                 vis[p[i].v]=true; 92                 q.push(p[i].v); 93             } 94         } 95     } 96     return true; 97 } 98 long long slove() 99 {100     int u,v,c;101     init();102     for (int i=1;i<=m;i++)103     {104         scanf("%d%d%d",&u,&v,&c);105         addEdge(u,v,c);106         raddEdge(v,u,c);107     }108     long long ans=0;109     spfa(x,head,next,p);110     for (int i=1;i<=n;i++)111     {112         cost[i]=dis[i];113         //printf("dis[%d]=%d\n",i,dis[i]);114     }115     spfa(x,rhead,rnext,rp);116     for (int i=1;i<=n;i++)117     {118         //printf("cost[%d]=%d\n",i,dis[i]);119         if (cost[i]+dis[i]>ans)120         ans=cost[i]+dis[i];121     }122     return ans;123 }124 int main()125 {126     while (scanf("%d%d%d",&n,&m,&x)!=EOF)127     {128         __int64 ans=slove();129         printf("%I64d\n",ans);130     }131     return 0;132 }