Dijkstra序列
作者:
我是高情商
,
2024-11-01 19:09:54
,
所有人可见
,
阅读 1
//Dijkstra序列等价于单调递增
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010,INF=0x3f3f3f3f;
int n,m;
int dist[N],g[N][N];
bool st[N];
int q[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);
while (m -- ){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=c;
}
int k;
cin>>k;
while(k--)
{
for(int i=0;i<n;i++)cin>>q[i];
if(dijkstra())puts("Yes");
else puts("No");
}
return 0;
}