题解 P4943 【密室】

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 表示第一眼看到题是个水题. emmm 结果发现自己错了. 然后突然发现不卡数组,不卡时间. ~~于是我就跑了6遍正常人都是跑4遍的~~ 这题坑点在于会存在4种情况 1. 哈利到$x$,罗恩到$y$ 2. 哈利到$y$.罗恩到$x$ 3. 哈利不动,罗恩走遍$x,y$ 4. 罗恩不动,哈利走遍$x,y$ 蒟蒻表示只考虑到了前两种. 还是大佬[@_王小呆](https://www.cnblogs.com/wangxiaodai/)强啊 orz 然后就跑$6$遍$dijkstra$! 还改了好久的 qwq ``代码`` ```c++ #include<cstdio> #include<algorithm> #include<queue> #include<iostream> #define int long long #define R register #define N 50008 using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,m,k; int head[N],tot,a,b; int dis[N],diss[N],disss[N],dissss[N]; int ans1,ans2,ans3,ans4,ans5,ans6; int ans7,ans8,ans=21474836476666666LL; struct cod{int u,v,w;}edge[N<<2]; struct hop { int u,d; bool operator <(const hop&a)const { return d>a.d; } }; bool vis[N],ok[N]; inline void add(int x,int y,int z) { edge[++tot].u=head[x]; edge[tot].v=y; edge[tot].w=z; head[x]=tot; } inline void dij(int s,int ds[],bool flg) { for(R int i=1;i<=n;i++)ds[i]=21474836476666LL,vis[i]=false; priority_queue<hop>q; q.push((hop){s,0});ds[s]=0; while(!q.empty()) { int u=q.top().u;q.pop(); if(vis[u])continue; vis[u]=true; for(R int i=head[u];i;i=edge[i].u) { if(ok[edge[i].v] and !flg)continue; if(!vis[edge[i].v] and ds[edge[i].v]>ds[u]+edge[i].w) { ds[edge[i].v]=ds[u]+edge[i].w; q.push((hop){edge[i].v,ds[edge[i].v]}); } } } } signed main() { in(n),in(m),in(k); for(R int i=1,x;i<=k;i++)in(x),ok[x]=true; for(R int i=1,x,y,z;i<=m;i++) { in(x),in(y),in(z); add(x,y,z);add(y,x,z); } in(a),in(b); dij(1,dis,1);//哈利. dij(1,diss,0); ans1=dis[a],ans2=dis[b]; ans3=diss[a],ans4=diss[b]; ans=min(ans,max(ans3,ans2)); ans=min(ans,max(ans1,ans4)); dij(a,disss,1);//哈利 dij(a,dissss,0); ans5=disss[b],ans6=dissss[b]; ans=min(ans,min(ans1+ans5,ans3+ans6)); dij(b,disss,1);//哈利 dij(b,dissss,0); ans7=disss[a],ans8=dissss[a]; ans=min(ans,min(ans2+ans7,ans4+ans8)); printf("%lld",ans); } ```