7-4 Dijkstra Sequence (30 分)

考查知识点：
Dijkstra算法
手动模拟一下就能看出规律

#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm> 
#include <vector> 
using namespace std;
const int N =1e3+3;
const int INF = 0x3f3f3f3f;
vector<int> tmp, path; 
int G[N][N];
int n, m;
int d[N]; 
bool Dijkstra(int s){
	fill(d, d+N, INF);
	bool vis[N] = {false}; 
	d[s] = 0;
	for(int i = 0; i < n; i++){
		int u = -1, Min = INF;
		for(int j = 1; j <= n; j ++){
			if(!vis[j] && d[j] < Min){
				u = j; 
				Min = d[j]; 
			}
		}
		if(u == -1 || d[u] != d[path[i]]) return false; 
		vis[u] = true;
		for(int v = 1; v <= n; v++){
			if(!vis[v] && G[u][v] + d[u] < d[v] ){
				d[v] =  G[u][v] + d[u]; 
			}
		} 
	}
	return true; 
} 


int main(){
	cin>>n>>m;
	int u, v, w; 
	fill(G[0], G[0]+N*N, INF); 
	while(m--){
		cin>>u>>v>>w;
		G[u][v] = w;
		G[v][u] = w; 
	}
	int k, x; 
	cin>>k;
	while(k--){
	 	 path.clear();
	 	 tmp.clear(); 
		 for(int i = 0; i < n; i ++){
		 	cin>>x;
			path.push_back(x); 
		 } 
		 if(Dijkstra(path[0])) cout<<"Yes"<<endl;
		 else cout<<"No"<<endl; 
	 } 
}