解题思路
图的存储
由于图的顶点的编号是1~N, 因此我们只需要存储边即可
用一个方阵来存储边, 给方阵的大小设为Max+1*Max+1, 正好能容纳所有结点
#define MaxVexNum 1000
unsigned edge[MaxVexNum+1][MaxVexNum+1];
信息读入
在main函数中读入顶点数N和边数M, 另起一个函数来读入边的信息
void InputGraph(int M){
int v1, v2, weight;
for(int i=0; i<M; i++){
scanf("%d%d%d", &v1, &v2, &weight);
edge[v1][v2] = edge[v2][v1] = weight;
}
}
dijkstra算法
不过多解释算法, 算法原理移步 dijkstra
很常规的, 我们用一个visited数组来记录顶点是否已被选入集合中(初始全为false), 再用一个数组MinDestance(初始全为无穷大, 即不可达)来保存当前所有顶点到源顶点的距离.
unsigned Visited[MaxVexNum+1];
unsigned MinDistance[MaxVexNum+1];
dijkstra算法中最关键的一步就是选择当前不在集合中且与源点距离最小的一个顶点出来, 即为SelectMin, 顶点被选择的顺序即为dijkstra序列. 在本题中我们任务是判断dijkstra序列是否正确, 所以我们可以另辟蹊径, 直接判断当前输入的顶点是不是要选择的, 也就是当前输入的顶点是否是不在集合中且在所有不在集合的顶点中距源点最近.
给出判断函数
int IsMin(int v, int N){
if(Visited[v]){
return 0;
}
for(int i=1; i<=N; i++){
//如果有某个不在集合中的顶点到源点的距离比v小, 说明v不是应该被选择的那个
if(!Visited[i] && MinDistance[i]<MinDistance[v]){
return 0;
}
}
return 1;
}
因为第一个输入是源点, 不可能出错, 并且dijkstra算法需要预先给出源点, 所以我们对源点进行单独处理
以下是完整的dijkstra函数
void Dijkstra(int start, int N){
MinDistance[start] = 0;
Visited[start] = 1;
for(int j=1; j<=N; j++){
if(edge[start][j] != 0){
MinDistance[j] = edge[start][j];
}
}
int InputV;
for(int i=2; i<=N; i++){
scanf("%d", &InputV);
//只有有一个判断为错误, 程序就可以结束了
if(!IsMin(InputV, N)){
printf("No\n");
while(++i <= N){//把剩下几个数都读完
scanf("%d", &InputV);
}
return;
}
//
Visited[InputV] = 1;
for(int j=1; j<=N; j++){
if(edge[InputV][j] != 0 && edge[InputV][j]+MinDistance[InputV] < MinDistance[j]){
MinDistance[j] = edge[InputV][j] + MinDistance[InputV];
}
}
}
printf("Yes\n");
}
在每次执行dijkstra算法前我们都要对两个辅助数组进行初始化
void MakeEmpty(int N){
for(int i=1; i<=N; i++){
Visited[i] = 0;
MinDistance[i] = Inf;
}
}
完整程序
#include <stdio.h>
#define MaxVexNum 1000
#define Inf __INT_MAX__
unsigned edge[MaxVexNum+1][MaxVexNum+1];
unsigned Visited[MaxVexNum+1];
unsigned MinDistance[MaxVexNum+1];
void MakeEmpty(int N){
for(int i=1; i<=N; i++){
Visited[i] = 0;
MinDistance[i] = Inf;
}
}
int IsMin(int v, int N){
if(Visited[v]){
return 0;
}
for(int i=1; i<=N; i++){
if(!Visited[i] && MinDistance[i]<MinDistance[v]){
return 0;
}
}
return 1;
}
void Dijkstra(int start, int N){
MinDistance[start] = 0;
Visited[start] = 1;
for(int j=1; j<=N; j++){
if(edge[start][j] != 0){
MinDistance[j] = edge[start][j];
}
}
int InputV;
for(int i=2; i<=N; i++){
scanf("%d", &InputV);
//匹配失败
if(!IsMin(InputV, N)){
printf("No\n");
while(++i <= N){
scanf("%d", &InputV);
}
return;
}
//
Visited[InputV] = 1;
for(int j=1; j<=N; j++){
if(edge[InputV][j] != 0 && edge[InputV][j]+MinDistance[InputV] < MinDistance[j]){
MinDistance[j] = edge[InputV][j] + MinDistance[InputV];
}
}
}
printf("Yes\n");
}
void InputGraph(int M){
int v1, v2, weight;
for(int i=0; i<M; i++){
scanf("%d%d%d", &v1, &v2, &weight);
edge[v1][v2] = edge[v2][v1] = weight;
}
}
int main(void){
int N, M;
scanf("%d%d", &N, &M);
InputGraph(M);
int K, start;
scanf("%d", &K);
for(int i=0; i<K; i++){
scanf("%d", &start);
MakeEmpty(N);
Dijkstra(start, N);
}
}