现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出?1，表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12同笔者其他文章一样，
在完成这道题之前， 首先要对构迪杰斯特拉算法的框架有一定的理解。
之后再根据题目的要求进行恰当的修改。
框架代码：
#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;#define INFINITY 32767typedef struct
{int *vexs; //顶点表int **arc; //邻接矩阵，可看作边表int numVertexes,numEdges; //图中当前的顶点数和边数
}MGraph;MGraph* InitGraph(int numVer,int numEdge)
{MGraph *G;G = (MGraph*)malloc(sizeof(MGraph));G->vexs = (int*)malloc(sizeof(int)*numVer);G->arc = (int**)malloc(sizeof(int*)*numVer);for(int i=0;i<numVer;i++){G->vexs[i]=i;G->arc[i] = (int*)malloc(sizeof(int)*numVer);for(int j=0;j<numVer;j++){if(i==j)G->arc[i][j] = 0;else G->arc[i][j] = INFINITY;}}G->numVertexes = numVer;G->numEdges = numEdge;return G;
}int GetMin(MGraph *G,int *s,int *d)
{int min=INFINITY;int index;for(int i=0;i<G->numVertexes;i++){if(s[i]==0 && d[i]<min){min = d[i];index = i;}}return index;
}void Dijkstra(MGraph *G,int index)
{int *s = (int*)malloc(sizeof(int)*G->numVertexes);int *p = (int*)malloc(sizeof(int)*G->numVertexes);int *d = (int*)malloc(sizeof(int)*G->numVertexes);for(int i=0;i<G->numVertexes;i++) //初始化辅助数组{if(G->arc[index][i]>0 && G->arc[index][i]!=INFINITY){p[i] = index;d[i] = G->arc[index][i];} else {p[i] = -1;d[i] = INFINITY;}if(i==index){s[i]=1;d[i]=0;}elses[i]=0;}for(int i=0;i<G->numVertexes;i++){int index = GetMin(G,s,d);s[index] = 1;for(int j=0;j<G->numVertexes;j++){if(s[j]==0 && d[index] + G->arc[index][j] < d[j]){d[j] = d[index] + G->arc[index][j];p[j] = index;}}}}int main()
{MGraph *G;int N,M;cin>>N>>M;G = InitGraph(N,M);for(int i=0;i<M;i++){int x,y,weight;cin>>x>>y>>weight;G->arc[x-1][y-1] = weight;}Dijkstra(G,0);return 0;
}Dijsktra()函数中3个辅助数组：
- S数组:记录了目标顶点到其他顶点的最短路径是否求得（1表示已求得，0表示为求得）
- P数组:记录了目标顶点到其他顶点的最短路径的前驱节点（-1表示无前驱，否则为编号）
- D数组:记录了目标顶点到其他顶点的最短路径的长度
附上本题完整代码：
#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;#define INFINITY 32767typedef struct
{int *vexs; //顶点表int **arc; //邻接矩阵，可看作边表int numVertexes,numEdges; //图中当前的顶点数和边数
}MGraph;MGraph* InitGraph(int numVer,int numEdge)
{MGraph *G;G = (MGraph*)malloc(sizeof(MGraph));G->vexs = (int*)malloc(sizeof(int)*numVer);G->arc = (int**)malloc(sizeof(int*)*numVer);for(int i=0;i<numVer;i++){G->vexs[i]=i;G->arc[i] = (int*)malloc(sizeof(int)*numVer);for(int j=0;j<numVer;j++){if(i==j)G->arc[i][j] = 0;else G->arc[i][j] = INFINITY;}}G->numVertexes = numVer;G->numEdges = numEdge;return G;
}int GetMin(MGraph *G,int *s,int *d)
{int min=INFINITY;int index;for(int i=0;i<G->numVertexes;i++){if(s[i]==0 && d[i]<min){min = d[i];index = i;}}return index;
}int* Dijkstra(MGraph *G,int index,int end)
{int *s = (int*)malloc(sizeof(int)*G->numVertexes);int *p = (int*)malloc(sizeof(int)*G->numVertexes);int *d = (int*)malloc(sizeof(int)*G->numVertexes);for(int i=0;i<G->numVertexes;i++) //初始化辅助数组{if(G->arc[index][i]>0 && G->arc[index][i]!=INFINITY){p[i] = index;d[i] = G->arc[index][i];} else {p[i] = -1;d[i] = INFINITY;}if(i==index){s[i]=1;d[i]=0;}elses[i]=0;}for(int i=0;i<G->numVertexes;i++){int index = GetMin(G,s,d);s[index] = 1;for(int j=0;j<G->numVertexes;j++){if(s[j]==0 && d[index] + G->arc[index][j] < d[j]){d[j] = d[index] + G->arc[index][j];p[j] = index;}}}int *road;road = (int*)malloc(sizeof(int)*30);int i=end,cnt=2;while(i!=-1) //用p数组找路径{road[cnt]=i;i=p[i];cnt++;}road[1]=d[end]; //数组road[1]存最短路径road[0]=cnt-1; //数组road[0]存总的路径数//这样便于在主函数中对边time和length的路径是否相同//也就是真正的路径是从2开始，从cnt倒叙开始，cnt个数return road;}int main()
{MGraph *G_length;MGraph *G_time;int N,M;cin>>N>>M;G_length = InitGraph(N,M);G_time = InitGraph(N,M);for(int i=0;i<M;i++){int x,y,way,length,time;cin>>x>>y>>way>>length>>time;if(way==1){G_length->arc[x][y] = length;G_time->arc[x][y] = time;}else{G_length->arc[x][y] = length;G_length->arc[y][x] = length;G_time->arc[x][y] = time;G_time->arc[y][x] = time;}}int start,end;cin>>start>>end;int *road_length,*road_time;//cout<<endl<<"Time = ";road_time = Dijkstra(G_time,start,end);//cout<<endl<<"Distance = ";road_length = Dijkstra(G_length,start,end);//总之运行完算法，返回，想办法满足题目要求的输出即可。int flag = 0; //0表示两条路线不一样，1表示两条路线一样if(road_length[0] == road_time[0]){int j;for(j=2;j<road_length[0]+2;j++){if(road_length[j]!=road_time[j])break;}if(j==road_length[0]+2)flag=1;}if(flag==1){printf("Time = %d; Distance = %d:",road_time[1],road_length[1]);for(int j=road_time[0];j>=2;j--){if(j!=2)printf(" %d =>",road_time[j]);else printf(" %d",road_time[j]);}}else{cout<<endl<<"Time = "<<road_time[1]<<":";for(int j=road_time[0];j>=2;j--){if(j!=2)printf(" %d =>",road_time[j]);else printf(" %d",road_time[j]);}cout<<endl<<"Distance = "<<road_length[1]<<":";for(int j=road_length[0];j>=2;j--){if(j!=2)printf(" %d =>",road_length[j]);else printf(" %d",road_length[j]);}}return 0;
}总结：
主要学习迪杰斯特拉算法的写法。针对于本题，就是对迪杰斯特拉算法的应用。为满足题目要求，本代码虽能够实现，但是逻辑较差，阅读代码稍微较困难。