;const int inf=1<<20;const int N=100024;struct node{int to,w;node* next;};node* edge[N];node* reedge[N];int n,m,x,dist[N],inq[N],q[N];void spfa(int flag){int i,u,h=0,t=1;node* ptr;for(i=0; i<=n; i++){dist[i]=inf;inq[i]=0;}dist[x]=0;inq[x]=1;q[0]=x;while(h!=t){u=q[h];h++;inq[u]=0;if(flag==1) ptr=edge[u];else ptr=reedge[u];while(ptr){if(dist[ptr->to]>(dist[u]+ptr->w)){dist[ptr->to]=dist[u]+ptr->w;if(inq[ptr->to]==0){q[t]=ptr->to;t++;inq[ptr->to]=1;}}ptr=ptr->next;}}}int main(){int i,u,v,w,ans[N],maxans;while(~scanf(“%d%d%d”,&n,&m,&x)){for(i=0; i<N; i++){edge[i]=NULL;reedge[i]=NULL;}for(i=0; i<m; i++){scanf(“%d%d%d”,&v,&u,&w);node *temp;temp= new node;temp->to=u;temp->w=w;temp->next=NULL;if(edge[v]==NULL){edge[v]=temp;}else{temp->next=edge[v];edge[v]=temp;}temp= new node;temp->to=v;temp->w=w;temp->next=NULL;if(reedge[u]==NULL){reedge[u]=temp;}else{temp->next=reedge[u];reedge[u]=temp;}}maxans=0;memset(ans,0,sizeof(ans));spfa(1);for(i=1; i<=n; i++){if(i!=x) ans[i]+=dist[i];}spfa(0);for(i=1; i<=n; i++){if(i!=x) ans[i]+=dist[i];maxans=max(ans[i],maxans);}printf(“%d\n”,maxans);}return 0;}
，当你见过了世界上最美丽的风景，
