dijkstra在线判断最优顺序
$O(k * n * n)$(最坏情况)
无论朴素方法还是堆优化版,都可以过。
使用朴素版,稠密图通过邻接矩阵建边,通过判断每一步是否正确来验证定义的序列。
这样问题就迎刃而解。
AC code
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int n,m;
int dist[N][N];
int ith[N];
int st[N],d[N];
bool dijkstra(int s)
{
memset(st,0,sizeof st);
memset(d,0x3f,sizeof d);
d[s]=0;
for(int i=0;i<n;i++)
{
int t=ith[i]; //将序列中的数一一带进去
for(int j=1;j<=n;j++)
if(!st[j]&&d[j]<d[t]) return false; //如果发现不是最优解,返回否
st[t]=1;
for(int j=1;j<=n;j++) d[j]=min(d[j],d[t]+dist[t][j]);
}
return true; //顺利通过,返回是
}
int main()
{
cin>>n>>m;
memset(dist,0x3f,sizeof dist);
while(m--)
{
int a,b,c; cin>>a>>b>>c;
dist[a][b]=dist[b][a]=c;
}
int q; cin>>q;
while(q--)
{
for(int i=0;i<n;i++) cin>>ith[i];
puts(dijkstra(ith[0])?"Yes":"No");
}
return 0;
}