PAT A 2019年秋季 7-4 Dijkstra Sequence AC代碼

一道dijkstra算法的模闆題

對于所謂的Dijkstra Sequence，直接判斷給出結點序列到起點距離(d[x])是否是不嚴格增序(<=)即可，這樣隻需要用模闆，再判斷距離是否不嚴格遞增即可。

對于這一點，我的了解是：

根據dijkstra算法思想原理，算法每一輪會确定一個離起點最近的點的距離，并把這個點作為這一輪的間接點，是以算法依次取到的間接點，一定是标記為未确定的餘下所有點中，到起點距離最近的點（而可能有多個點距離都是最近，是以産生了不同的序列），是以這就保證了取到的間接點序列到起點的距離是不嚴格遞增的。并且隻要是不嚴格遞增的，就可以是間接點取到的順序。

#include<iostream>
#include<vector>
using namespace std;
int Nv,Ne,K;
int inf=1000000000;
int G[1001][1001];
int d[1001];
void dijkstra(int s){
	fill(d,d+1001,inf);	
	int visit[1001]={0};
	d[s]=0;
	for(int i=1;i<=Nv;i++){
		int min=inf,u=-1;
		for(int j=1;j<=Nv;j++){
			if(visit[j]==0&&d[j]<min){
				min=d[j];
				u=j;
			}
		}
		if(u==-1) return;
		visit[u]=1;
		for(int v=1;v<=Nv;v++){
			if(G[u][v]+d[u]<d[v]&&G[u][v]!=inf&&visit[v]==0){
				d[v]=G[u][v]+d[u];
			}
		}
	}
}
int main(){
	fill(G[0],G[0]+1001*1001,inf);
	cin>>Nv>>Ne;
	for(int i=0;i<Ne;i++){
		int a,b,s;
		scanf("%d %d %d",&a,&b,&s);
		G[a][b]=s;
		G[b][a]=s;
	}
	cin>>K;
	for(int i=0;i<K;i++){
		bool flag=true;
		int start;
		scanf("%d",&start);
		vector<int> v;
		v.push_back(start);
		for(int j=1;j<Nv;j++){
			int index;
			scanf("%d",&index);
			v.push_back(index);
		}
		dijkstra(start);
		for(int j=1;j<v.size();j++){
			if(d[v[j-1]]>d[v[j]]){
				flag=false;
				break;
			}
		}
		if(flag){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	return 0;
}