公園

圖論+dijkstra

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
vector<ll> v[40005];
//a、b、c分別是小度、度度熊、終點到各個點的最短距離
ll a[40005],b[40005],c[40005],dist[40005],st[40005];
void dij(ll idx,ll e)
{memset(st,0,sizeof(st));memset(dist,0x3f,sizeof(dist));dist[idx]=0;priority_queue<pii,vector<pii>,greater<pii>> q;q.push({0,idx});while(!q.empty()){pii p=q.top();q.pop();ll a=p.first;ll b=p.second;if(st[b]) continue;st[b]=1;for(ll i=0;i<v[b].size();i++){ll c=v[b][i];if(dist[c]>a+e){dist[c]=a+e;q.push({dist[c],c});}}}
}
int main()
{ll te,fe,s,t,f,n,m;cin>>te>>fe>>s>>t>>f>>n>>m;for(int i=0;i<m;i++){ll a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}dij(t,te);for(ll i=1;i<=n;i++) a[i]=dist[i];dij(f,fe);for(ll i=1;i<=n;i++) b[i]=dist[i];dij(n,fe+te-s);for(ll i=1;i<=n;i++) c[i]=dist[i];ll res=0x3f3f3f3f;for(ll i=1;i<=n;i++){if(a[i]>=0x3f3f3f3f||b[i]>=0x3f3f3f3f||c[i]>=0x3f3f3f3f) continue;res=min(res,a[i]+b[i]+c[i]);}if(res>=0x3f3f3f3f) cout<<-1<<endl;else cout<<res<<endl;return 0;
}