分析
考虑答案只可能是分别到或者哈利一个人到两个房间,
那么在罗恩的时候先不建不可走的边,等到哈利走的时候再建边
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=50011;
struct node{int y,w,next;}e[N<<2];
struct rec{int x,y,w;}b[N<<1]; pair<int,int>heap[N];
int Cnt,dis[N],as[N],v[N],zx,zy,n,m,tot,et,ans0,ans1,ans2,ans3,ans4;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed min(int a,int b){return a<b?a:b;}
inline signed max(int a,int b){return a>b?a:b;}
inline void Push(pair<int,int>w){
heap[++Cnt]=w;
rr int x=Cnt;
while (x>1){
if (heap[x]<heap[x>>1])
swap(heap[x],heap[x>>1]),x>>=1;
else return;
}
}
inline void Pop(){
heap[1]=heap[Cnt--];
rr int x=1;
while ((x<<1)<=Cnt){
rr int y=x<<1;
if (y<Cnt&&heap[y+1]<heap[y]) ++y;
if (heap[x]>heap[y]) swap(heap[x],heap[y]),x=y;
else return;
}
}
inline void Dijkstra(int S){
heap[++Cnt]=make_pair(0,S);
for (rr int i=1;i<=n;++i) dis[i]=1e9+7; dis[S]=0;
while (Cnt){
rr int t=heap[1].first,x=heap[1].second;
Pop(); if (t!=dis[x]) continue;
for (rr int i=as[x];i;i=e[i].next)
if (dis[e[i].y]>dis[x]+e[i].w){
dis[e[i].y]=dis[x]+e[i].w;
Push(make_pair(dis[e[i].y],e[i].y));
}
}
}
signed main(){
n=iut(),m=iut();
for (rr int i=1;i<=n;++i) v[i]=1;
for (rr int T=iut();T;--T) v[iut()]=0;
for (rr int i=1;i<=m;++i){
rr int x=iut(),y=iut(),w=iut();
if (!v[x]||!v[y]) b[++tot]=(rec){x,y,w};
else{
e[++et]=(node){y,w,as[x]},as[x]=et;
e[++et]=(node){x,w,as[y]},as[y]=et;
}
}
zx=iut(),zy=iut(),Dijkstra(1),ans0=dis[zx],ans1=dis[zy];
for (rr int i=1;i<=tot;++i)
e[++et]=(node){b[i].y,b[i].w,as[b[i].x]},as[b[i].x]=et,
e[++et]=(node){b[i].x,b[i].w,as[b[i].y]},as[b[i].y]=et;
Dijkstra(1),ans2=dis[zx],ans3=dis[zy],Dijkstra(zx),ans4=dis[zy];
rr int alter=min(max(ans0,ans3),max(ans1,ans2)),with=min(ans2,ans3)+ans4;
return !printf("%d",min(alter,with));
}