题解 P4943 【密室】
顾z
2018-10-28 20:11:57
# [顾](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);
}
```