题解 | #[USACO 2010 Dec S]Apple Delivery#

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxm 100010
const ll inf=1e12;
int n;
struct node{
    ll p,w;
    bool operator <(const node &u)const{
        return u.w<w;
    }
};
ll dist[maxm];
vector<node>G[maxm];
ll dijk(int s,int t,int k){
    for(int i=1;i<=n;i++)dist[i]=inf;
    priority_queue<node>q;
    dist[s]=0;
    q.push({s,0});
    while(q.empty()==false){
        int u=q.top().p;q.pop();
        for(int i=0;i<(int)G[u].size();i++){
            int v=G[u][i].p,w=G[u][i].w;
            if(v!=k&&dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
                q.push({v,dist[v]});
            }
        }
    }
    return dist[t];
}
int main(){
    int m,s,t1,t2;
    cin>>m>>n>>s>>t1>>t2;
    while(m--){
        ll x,y,w;
        scanf("%lld%lld%lld",&x,&y,&w);
        G[x].push_back({y,w});
        G[y].push_back({x,w});
    }
    ll res=dijk(s,t1,t2)+dijk(t1,t2,s);
    res=min(res,dijk(s,t2,t1)+dijk(t2,t1,s));
    cout<<res;
    return 0;
}

这道题要求必须经过a、b两点，我们很容易想到路径要么是s->a->b或者s->b->a

在计算s->a时不把b加入队列即可