题目链接： 传送门
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 2010; //g为邻接矩阵，d为当前点到其他点的最短距离 int g[N][N], d[N], n, m; //标记当前点是否已经是最短的了 bool checked[N]; //迪杰斯特拉算法模板 int dijkstra() { memset(d, 0x3f, sizeof(d)); d[1] = 0; for(int i = 0; i < n; i++) { int t = -1; for(int j = 1; j <= n; j++) if(!checked[j] && (t == -1 || d[t] > d[j])) t = j; checked[t] = 1; for(int j = 1; j <= n; j++) { d[j] = min(d[j],d[t] + g[t][j]); } } if(d[n] == 0x3f3f3f3f) return -1; else return d[n]; } int main() { scanf("%d%d", &m, &n); //把邻接矩阵初始化 memset(g, 0x3f, sizeof g); while (m--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); //这里防一手重复边（不写min没给过） g[a][b] = min(g[a][b], c); g[b][a] = min(g[b][a], c); } printf("%d\n", dijkstra()); return 0; }这是一道单源最短路径的模板题，直接套版做就好了，在输入时加个判断防止多次输入。 具体关于该算法的介绍请见：某大佬博客
