【题解】
其实解法
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 200010 7 using namespace std; 8 int n,m,s,ans,tot,last[N],dis[N],dis2[N],pos[N]; 9 struct rec{ 10 int u,v,d; 11 }r[N<<1]; 12 struct edge{ 13 int to,pre,dis; 14 }e[N<<1]; 15 struct heap{ 16 int poi,dis; 17 }h[N]; 18 inline int read(){ 19 int k=0,f=1; char c=getchar(); 20 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 21 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 22 return k*f; 23 } 24 inline void up(int x){ 25 int fa; 26 while((fa=(x>>1))&&h[fa].dis>h[x].dis){ 27 swap(h[fa],h[x]); swap(pos[h[fa].poi],pos[h[x].poi]); 28 x=fa; 29 } 30 } 31 inline void down(int x){ 32 int son; 33 while((son=(x<<1))<=tot){ 34 if(son<tot&&h[son].dis>h[son+1].dis) son++; 35 if(h[son].dis<h[x].dis){ 36 swap(h[son],h[x]); swap(pos[h[son].poi],pos[h[x].poi]); 37 x=son; 38 } 39 else return; 40 } 41 } 42 inline void dijkstra(int x){ 43 for(rg int i=1;i<=n*2;i++) dis[i]=1e9; 44 h[tot=pos[x]=1]=(heap){x,dis[x]=0}; 45 while(tot){ 46 int now=h[1].poi; h[1]=h[tot--]; if(tot) down(1); 47 for(rg int i=last[now],to;i;i=e[i].pre) 48 if(dis[to=e[i].to]>dis[now]+e[i].dis){ 49 dis[to]=dis[now]+e[i].dis; 50 if(!pos[to]) h[pos[to]=++tot]=(heap){to,dis[to]}; 51 else h[pos[to]].dis=dis[to]; 52 up(pos[to]); 53 } 54 pos[now]=0; 55 } 56 } 57 int main(){ 58 n=read(); m=read(); s=read(); 59 for(rg int i=1;i<=m;i++){ 60 int u=read(),v=read(),d=read(); 61 r[i]=(rec){u,v,d}; 62 e[++tot]=(edge){v,last[u],d}; last[u]=tot; 63 } 64 dijkstra(s); 65 for(rg int i=1;i<=n;i++) dis2[i]=dis[i]; 66 memset(last,0,sizeof(last)); 67 for(rg int i=1;i<=m;i++){ 68 int u=r[i].u,v=r[i].v,d=r[i].d; 69 e[++tot]=(edge){u,last[v],d}; last[v]=tot; 70 } 71 dijkstra(s); 72 for(rg int i=1;i<=n;i++) ans=max(ans,dis[i]+dis2[i]); 73 printf("%d ",ans); 74 return 0; 75 }
就是先做一遍最短路，把所有边反向，再做一遍最短路，最后找两次的dis之和的最大值。