【题解】
其实解法
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define rg register
#define N 200010
using namespace std;
int n,m,s,ans,tot,last[N],dis[N],dis2[N],pos[N];
struct rec{
int u,v,d;
}r[N<<];
struct edge{
int to,pre,dis;
}e[N<<];
struct heap{
int poi,dis;
}h[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
inline void up(int x){
int fa;
while((fa=(x>>))&&h[fa].dis>h[x].dis){
swap(h[fa],h[x]); swap(pos[h[fa].poi],pos[h[x].poi]);
x=fa;
}
}
inline void down(int x){
int son;
while((son=(x<<))<=tot){
if(son<tot&&h[son].dis>h[son+].dis) son++;
if(h[son].dis<h[x].dis){
swap(h[son],h[x]); swap(pos[h[son].poi],pos[h[x].poi]);
x=son;
}
else return;
}
}
inline void dijkstra(int x){
for(rg int i=;i<=n*;i++) dis[i]=1e9;
h[tot=pos[x]=]=(heap){x,dis[x]=};
while(tot){
int now=h[].poi; h[]=h[tot--]; if(tot) down();
for(rg 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]};
else h[pos[to]].dis=dis[to];
up(pos[to]);
}
pos[now]=;
}
}
int main(){
n=read(); m=read(); s=read();
for(rg int i=;i<=m;i++){
int u=read(),v=read(),d=read();
r[i]=(rec){u,v,d};
e[++tot]=(edge){v,last[u],d}; last[u]=tot;
}
dijkstra(s);
for(rg int i=;i<=n;i++) dis2[i]=dis[i];
memset(last,,sizeof(last));
for(rg int i=;i<=m;i++){
int u=r[i].u,v=r[i].v,d=r[i].d;
e[++tot]=(edge){u,last[v],d}; last[v]=tot;
}
dijkstra(s);
for(rg int i=;i<=n;i++) ans=max(ans,dis[i]+dis2[i]);
printf("%d\n",ans);
return ;
}
就是先做一遍最短路，把所有边反向，再做一遍最短路，最后找两次的dis之和的最大值。