#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define maxn 1001
#define maxm 100001
using namespace std;
struct graph{
struct edge{
int to,dis,next;
edge(){}
edge(const int &_to,const int &_dis,const int &_next){
to=_to,dis=_dis,next=_next;
}
}e[maxm];
int head[maxn],k;
inline void init(){ memset(head,-1,sizeof head); }
inline void add(const int &u,const int &v,const int &w){
e[k]=edge(v,w,head[u]),head[u]=k++;
}
}a,b;
int dis[maxn],ans[maxn];
bool vis[maxn];
int n,m,s;
priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > q;
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
inline void dijkstra(const graph &g){
memset(dis,0x3f,sizeof dis),memset(vis,false,sizeof vis);
q.push(make_pair(0,s)),dis[s]=0;
while(q.size()){
int u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=true;
for(register int i=g.head[u];~i;i=g.e[i].next){
int v=g.e[i].to;
if(dis[v]>dis[u]+g.e[i].dis){
dis[v]=dis[u]+g.e[i].dis;
q.push(make_pair(dis[v],v));
}
}
}
}
int main(){
a.init(),b.init();
n=read(),m=read(),s=read();
for(register int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
a.add(u,v,w),b.add(v,u,w);
}
dijkstra(a);
for(register int i=1;i<=n;i++) ans[i]+=dis[i];
dijkstra(b);
for(register int i=1;i<=n;i++) ans[i]+=dis[i];
int mmax=0;
for(register int i=1;i<=n;i++) mmax=max(mmax,ans[i]);
printf("%d\n",mmax);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章