这题只需抓住两条性质；
1）
不会出现上图情况，原因：两点之间，如果走最短路，那么一定是尽量走相同的路径
所以我们可以记录在两人最短路中的共同部分，找到形成最长的一条链，并且是单向边组成的链
2）
不会出现这种情况，即共同走过一段路后不可反向，原因：不符合最短路
所以考虑面对面走过的情况时，只需将其中一人的边反向即可
=================================================
代码如下（有些卡常）：
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #define pii pair<int,int> #define MAXE 5000005 #define MAXV 1505 using namespace std; int V,E,x1,y1,x2,y2; int Next[MAXE],first[MAXV],cnt; int from[MAXE],to[MAXE],val[MAXE]; priority_queue<pii,vector<pii >,greater<pii > > q; bool vv[2][MAXE]; vector<pii > G[MAXV]; int getin[MAXV]; void add(int u,int v,int w){ cnt++; Next[cnt]=first[u]; first[u]=cnt; from[cnt]=u; to[cnt]=v; val[cnt]=w; cnt++; Next[cnt]=first[v]; first[v]=cnt; from[cnt]=v; to[cnt]=u; val[cnt]=w; } void dijk(int x,int y,int ss){ int d1[MAXV],d2[MAXV]; memset(d1,0x7f,sizeof(d1)); memset(d2,0x7f,sizeof(d2)); d1[x]=0; q.push(make_pair(0,x)); while(!q.empty()){ pii p=q.top(); q.pop(); int u=p.second; if(d1[u]<p.first){ continue; } for(int e=first[u];e;e=Next[e]){ int v=to[e],w=val[e]; if(d1[v]>d1[u]+w){ d1[v]=d1[u]+w; q.push(make_pair(d1[v],v)); } } } d2[y]=0; q.push(make_pair(0,y)); while(!q.empty()){ pii p=q.top(); q.pop(); int u=p.second; if(d2[u]<p.first){ continue; } for(int e=first[u];e;e=Next[e]){ int v=to[e],w=val[e]; if(d2[v]>d2[u]+w){ d2[v]=d2[u]+w; q.push(make_pair(d2[v],v)); } } } int L=d2[x]; for(int i=1;i<=E;i++){ int u=from[i],v=to[i],w=val[i]; if(d1[u]+w+d2[v]==L){ vv[ss][i]=1; } } } int topo_sort(int u){ int ret=0; for(int i=0;i<G[u].size();i++){ int v=G[u][i].second,w=G[u][i].first; ret=max(ret,topo_sort(v)+w); } return ret; } void solve(){ dijk(x1,y1,0); dijk(x2,y2,1); for(int i=1;i<=E;i++){ if(vv[0][i]&&vv[1][i]){ int u=from[i],v=to[i],w=val[i]; getin[v]++; G[u].push_back(make_pair(w,v)); } } int ans=0; for(int i=1;i<=V;i++){ if(!getin[i]){ ans=max(ans,topo_sort(i)); } } for(int i=1;i<=V;i++){ G[i].clear(); } memset(getin,0,sizeof(getin)); memset(vv[1],false,sizeof(vv[1])); swap(x2,y2); dijk(x2,y2,1); for(int i=1;i<=E;i++){ if(vv[0][i]&&vv[1][i]){ int u=from[i],v=to[i],w=val[i]; getin[v]++; G[u].push_back(make_pair(w,v)); } } for(int i=1;i<=V;i++){ if(!getin[i]){ ans=max(ans,topo_sort(i)); } } printf("%d\n",ans); } int main() { // freopen("data.in","r",stdin); scanf("%d%d%d%d%d%d",&V,&E,&x1,&y1,&x2,&y2); for(int i=1;i<=E;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } E=(E<<1); solve(); return 0; }