AcWing 4275. Dijkstra序列
原题链接
简单
作者:
用并查集出你户籍
,
2023-02-09 10:17:20
,
所有人可见
,
阅读 160
//4275.迪杰斯特拉序列
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
bool st[N];
int g[N][N],dist[N],a[N],n,m,k;
//题干要求针对每给出的一个序列来判断这个序列是否合法,即判断每个“答案”是否正确
//判断的方法无非是将这个序列代入迪杰斯特拉算法,看看求出来的距离是否是最短的。
//已知迪杰斯特拉算法源于贪心,因此,在处理的过程中,每次仅考虑当前点到下一个位于序列中的点的距离,是否还有更短的
//一旦找的了一个更短的。就说明现在这个不合法,不合法的话就输出no
bool dij(int start)
{
//对于每个序列,都需要进行一次判断,因此 在判断之前要将前一个序列处理时所产生的污染去除
memset(dist,0x3f,sizeof dist);
memset(st,false,sizeof st);
dist[start] = 0;
st[start] = true;//表示序列的起始点已经走过了
for(int i = 1;i<=n;i++)//遍历迪杰斯特拉序列,从起点开始更新是因为要从起始点开始建立通往其他点的边
{
int t = a[i];
for(int j = 1;j<=n;j++)//循环遍历所有点
if(!st[j]&&dist[j]<dist[t])//找到了一个距离起始点更近的点j
return false;//寄了,返回false
//循环里一遍之后,没找到,那么t确实是最短的
st[t] = true;//那么这个点认为是走过了,赋值为true
for(int j =1;j<=n;j++)
if(dist[j]>dist[t]+g[t][j])
dist[j] = dist[t]+g[t][j];
}
return true;//所有点都是正确的,因此返回true
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = g[b][a] = c;
}
scanf("%d",&k);
while(k--)
{
for(int i =1;i<=n;i++)
scanf("%d",&a[i]);
if(dij(a[1]))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}