【题解】
最短路裸题。。
本题要求出每个点到终点走最短路来回的距离，因此我们先跑一遍最短路得出每个点到终点的最短距离，然后把边反向再跑一遍最短路，两次结果之和即是答案。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N (2010)
#define M (200010)
#define rg register
#define fa (x>>1)
using namespace std;
int n,m,x,tot,ans,dis[N],last[N],pos[N],sum[N];
struct edge{
int to,pre,dis;
}e[M];
struct heap{
int to,dis;
}h[N];
struct record{
int u,v,dis;
}rec[M];
inline int read(){
int k=0,f=1; char c=getchar();
while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
return k*f;
}
inline void add(int x,int y,int z){e[++tot]=(edge){y,last[x],z}; last[x]=tot;}
inline void up(int x){
while(x>1&&h[fa].dis>h[x].dis){
swap(h[fa],h[x]); swap(pos[h[fa].to],pos[h[x].to]);
x=fa;
}
}
inline void down(int x){
while(x<=(tot>>1)){
int son=x<<1;
if(son<tot&&h[son].dis>h[son+1].dis) son++;
if(h[son].dis<h[x].dis){
swap(h[son],h[x]); swap(pos[h[son].to],pos[h[x].to]);
x=son;
}
else return;
}
}
void dijkstra(int x){
h[pos[x]=tot=1]=(heap){x,dis[x]=0};
while(tot){
int now=h[1].to; h[1]=h[tot--]; if(tot) down(1);
for(int i=last[now],to;i;i=e[i].pre)
if(dis[to=e[i].to]>dis[now]+e[i].dis){
dis[to]=dis[now]+e[i].dis;
if(!pos[to]) h[pos[to]=++tot]=(heap){to,dis[to]};
up(pos[to]);
}
pos[now]=0;
}
}
inline void clear(){
memset(last,0,sizeof(last));
memset(dis,32,sizeof(dis));
memset(pos,0,sizeof(pos));
tot=0;
}
void out(){
for(int i=1;i<=n;i++) printf("%d ",dis[i]); puts("");
}
int main(){
n=read(); m=read(); x=read();
clear();
for(rg int i=1;i<=m;i++){
rec[i].u=read(); rec[i].v=read();
add(rec[i].u,rec[i].v,rec[i].dis=read());
}
dijkstra(x); //out();
for(int i=1;i<=n;i++) sum[i]=dis[i];
clear();
for(rg int i=1;i<=m;i++) add(rec[i].v,rec[i].u,rec[i].dis);
dijkstra(x); //out();
for(int i=1;i<=n;i++) ans=max(ans,sum[i]+dis[i]);
printf("%d\n",ans);
return 0;
}