题目很简单， n个点m条边，求所有点到1节点的最短路径。
dijkstra思想： 点与点之间要么是直接有边相连，要么是通过其他边过渡形成路径，dijkstra就是通过这种特性来对点与点之间进行松弛操作；
操作： 找到与1节点最短的那一条边，然后通过它来更新与这条边相邻的点的路径值，在找第二短的以此类推。。（注意dijkstra不能处理负权边）！！
代码如下：
#include<iostream>
using namespace std;
#define maxe 20
int e[maxe][maxe], vis[maxe], book[maxe] = {}, dis[maxe], n, m, inf = 9999999, x, y, z,u,min;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j)e[i][j] = 0;
else e[i][j] = inf;
}
}
for (int i = 1; i <= m; i++) {
cin >> x >> y >> z;
e[x][y] = z;
}
for (int i = 1; i <= n; i++) {
dis[i] = e[1][i];
}
for (int i = 1; i <= n; i++)
book[i] = 0;
book[1] = 1;
for (int i = 1; i <= n - 1; i++) {
min = inf;
for (int j = 1; j <= n; j++) {
if (book[j] == 0 && dis[j] < min) {
min = dis[j];
u = j;
}
}
book[u] = 1;
for (int v = 1; v <= n; v++) {
if (e[u][v] < inf) {
if (dis[v] > e[u][v] + dis[u])
dis[v] = dis[u] + e[u][v];
}
}
}
for (int i = 1; i <= n; i++)
cout << dis[i] << endl;
return 0;
}
赞一个谢谢
！！
