这题的关键在求其他所有点到$X$的最短路径. Floyd显然过不了. 冷静分析一波发现无向图中从某个点到$X$的最短路就等于从$X$到那个点的最短路, 有向图中所有边取反后也成立. 所以取反之后在求一次单源最短路就行了.
#include<cstdio> #include<cstring> #include<queue> #define re register #define in inline using namespace std; in int read() { int s(0),b(0);char ch; do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9'); while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); if(b)return -s; return s; } const int size=1005; int n,m,x,head[size],cnt,dis1[size],dis2[size],b[size],eu[100005],ev[100005],ew[100005]; struct edge{int t,w,nxt;}e[100005]; in void add(int f,int t,int w){e[++cnt].t=t,e[cnt].w=w,e[cnt].nxt=head[f],head[f]=cnt;} in void spfa(int dis[]) { memset(b,0,sizeof(b)); queue<int> q; while(!q.empty()) q.pop(); for(re int i=1;i<=n;++i) dis[i]=20000000; q.push(x); b[x]=1,dis[x]=0; while(!q.empty()) { int u=q.front();q.pop(); b[u]=0; for(re int i=head[u];i;i=e[i].nxt) { int v=e[i].t; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; if(!b[v]){b[v]=1;q.push(v);} } } } } signed main() { n=read(),m=read(),x=read(); for(re int i=1;i<=m;++i) { eu[i]=read(),ev[i]=read(),ew[i]=read(); add(eu[i],ev[i],ew[i]); } spfa(dis1); memset(head,0,sizeof(head)); memset(e,0,sizeof(e)); cnt=0; for(re int i=1;i<=m;++i) add(ev[i],eu[i],ew[i]); spfa(dis2); int ans=0; for(re int i=1;i<=n;++i) if(dis1[i]+dis2[i]>ans) ans=dis1[i]+dis2[i]; printf("%d\n",ans); return 0; }
最新评论