题解：AT_joi2018ho_d 定期券 (Commuter Pass)

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<utility>
#include<algorithm>
using namespace std;
const int N=2e5+5;
const int M=2e5+5;
int n,m,A,B,C,D,head[N],nxt[M<<1],to[M<<1],w[M<<1],cnt=0,indegree_new[N],indegree_rev[N];
long long disA[N],disB[N],disC[N],disD[N],min_new[N],min_rev[N],ans;
bool vis[N];
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>PQ;
vector<int>New[N],Rev[N];
queue<int>Q;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
void Add(int u,int v,int cost)
{
    to[++cnt]=v;
    w[cnt]=cost;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void Dijkstra(int st,long long dis[])
{
    for(int i=1;i<=n;i++)
        vis[i]=false,dis[i]=0x3f3f3f3f3f3f3f3f;
    while(!PQ.empty()) PQ.pop();
    dis[st]=0;
    PQ.push({dis[st],st});
    while(!PQ.empty())
    {
        int u=PQ.top().second;
        PQ.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];i;i=nxt[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]+w[i])
            {
                dis[v]=dis[u]+w[i];
                PQ.push({dis[v],v});
            }
        }
    }
}
void BuildNewGraph()
{
    for(int u=1;u<=n;u++)
    {
        for(int i=head[u];i;i=nxt[i])
        {
            int v=to[i];
            if(disA[u]+w[i]+disB[v]==disA[B])
            {
                New[u].push_back(v);
                indegree_new[v]++;
                Rev[v].push_back(u);
                indegree_rev[u]++;
            }
        }
    }
}
int main()
{
    // freopen("mission.in","r",stdin);
    // freopen("mission.out","w",stdout);
    ios::sync_with_stdio(false),cout.tie(0);
    n=read(),m=read(),A=read(),B=read(),C=read(),D=read();
    for(int i=1;i<=m;i++)
    {
        int u,v,cost;
        u=read(),v=read(),cost=read();
        Add(u,v,cost),Add(v,u,cost);
    }
    Dijkstra(A,disA),Dijkstra(B,disB),Dijkstra(C,disC),Dijkstra(D,disD);
    ans=disC[D];
    BuildNewGraph();
    for(int i=1;i<=n;i++)
    {
        min_new[i]=disC[i];
        if(!indegree_new[i]) Q.push(i);
    }
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int v:New[u])
        {
            min_new[v]=min(min_new[v],min_new[u]);
            indegree_new[v]--;
            if(!indegree_new[v]) Q.push(v);
        }
    }
    while(!Q.empty()) Q.pop();
    for(int i=1;i<=n;i++)
    {
        min_rev[i]=disC[i];
        if(!indegree_rev[i]) Q.push(i);
    }
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int v:Rev[u])
        {
            min_rev[v]=min(min_rev[v],min_rev[u]);
            indegree_rev[v]--;
            if(!indegree_rev[v]) Q.push(v);
        }
    }
    for(int i=1;i<=n;i++)
        ans=min({ans,min_new[i]+disD[i],min_rev[i]+disD[i]});
    cout<<ans<<'\n';
    return 0;
}