可以照图输入数据进行验证
从1到6的最短路为 9 依然是朴素的代码
///最短路（Dijkstra 迪杰斯特拉算法） ***该算法中不能出现负权值*** #include<cstdio> #define MAX 0x3f3f3f3f using namespace std; int main() { int n; scanf("%d",&n); ///printf("几组数据\n"); while(n--) { int m; scanf("%d",&m); ///printf("有几个节点\n"); int map[m+5][m+5]; for(int i=1; i<=m; i++) { for(int u=1; u<=m; u++) { map[i][u]=MAX; ///先吧所有节点之间的距离变为无限大(表示不相连) } } for(int i=1; i<=m; i++) { int e,in,len; scanf("%d",&e); ///printf("第%d个节点与几个节点相连？\n",i); for(int u=1; u<=e; u++) { scanf("%d %d",&in,&len); ///printf("与谁相连，距离为多少\n"); map[i][in]=len; } } int vis[m+5]; ///v数组用来标记是否已经访问过 for(int i=1; i<=m; i++) { vis[i]=0; } int dis[m+5]; ///dis数组用来储存每个点与起始点的“实时”最短距离(间接或直接) int ben,end; scanf("%d %d",&ben,&end); ///printf("输入起点和终点\n"); for(int i=1; i<=m; i++) { dis[i]=map[ben][i]; ///对dis数组初始化一下 } vis[ben]=1; ///从起始点开始遍历，起始点变为访问过，起始点与起始点之间的距离为0； dis[ben]=0; int p; ///p用来记录下一个加入的点 for(int i=1; i<=m-1; i++) ///除了第一个点外，需要再遍历m-1个点才能遍历整个图 { int min=MAX; for(int j=1; j<=m; j++) ///用来找出下一个到距离(直接或间接)起始点最近的未访问的点 { if(!vis[j]&&min>dis[j]) { min=dis[j]; p=j; } } vis[p]=1; ///找到以后将其标为访问过 for(int j=1; j<=m; j++) ///因为又加入了一个点，所以其他点距离起始点的最短距离可以进行更新 { if(!vis[j]&&min+map[p][j]<dis[j]) ///通过新点到起始点的距离小于以前的最优解，那么更新数据 { dis[j]=min+map[p][j]; } } } printf("%d\n",dis[end]); ///最后输出最短距离(原则上可以输出任意终点的最短路) } return 0; }