AcWing 4275. Dijkstra序列
原题链接
简单
作者:
YAX_AC
,
2024-12-10 21:35:10
,
所有人可见
,
阅读 4
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int n,m,k;
int g[N][N];
int q[N];
int dist[N],st[N];
bool dijkstra()
{
memset(dist,0x3f,sizeof dist);
memset(st,0,sizeof st);
dist[q[0]] = 0;
for(int i = 0; i<n; i++)
{
int t = q[i];
for(int j = 1; j<=n; j++)
{
if(!st[j] && dist[j] < dist[t])
return false;
}
st[t] = true;
for(int j = 1; j<=n; j++)
{
dist[j] = min(dist[j],dist[t]+g[t][j]);
}
}
return true;
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i = 0; i<m; i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b] = g[b][a] = c;
}
cin>>k;
while(k--)
{
for(int i = 0; i<n; i++) cin>>q[i];
if(dijkstra()) puts("Yes");
else puts("No");
}
return 0;
}