Description
密室被打开了。
哈利与罗恩进入了密室，他们发现密室由n个小室组成，所有小室编号分别为：1,2,...,n。所有小室之间有m条通道，对任意两个不同小室最多只有一条通道连接，而每通过一条通道都需要Ci 的时间。
开始时哈利与罗恩都在编号为1的小室里，他们的目标是拯救金妮和寻找日记，但是他们发现金妮和日记可能在两个不同的小室里，为了尽快发现真相，他们决定以最少的时间到达两个目标小室。但是某些小室只有会与蛇对话的人才能进入，也就是只有哈利一个人可以进入。
现在，哈利告诉你密室的结构，请你计算他们到达两个目标小室的最短时间。
Input
第一行 n,m,k 表示有n个小室m条通道，k间小室只有哈利可以进入。
第二行 k 个数，表示只有哈利可以进入的小室的编号。（若k=0，不包含该行）
接下来m行，每行3个数：a,b,c 表示a小室与b小室之间有一条需要花费c时间的通道。
最后一行，两个数 x,y 表示哈利与罗恩需要去的小室的编号
Output
一行，输出一个数，表示到达两个密室的最短时间。
表示第一眼看到题是个傻逼题. emmm
结果发现自己错了.
然后突然发现不卡数组,不卡时间.
于是我就跑了6遍
正常人都是跑4遍的emmm
这题坑点在于会存在4种情况
- 哈利到(x),罗恩到(y)
- 哈利到(y).罗恩到(x)
- 哈利不动,罗恩走遍(x,y)
- 罗恩不动,哈利走遍(x,y)
蒟蒻表示只考虑到了前两种.
还是大佬@_王小呆强啊 orz
然后就跑(6)遍(dijkstra)!
还改了好久的 qwq
代码
#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);
}