（重刷）HDU 1874 畅通工程续 + HDU 2544 最短路 最短路水题，dijkstra解法。

floyd解法

今天初看dijkstra，先拿这两题练手，其他变形题还是不是很懂。

模版题，纯练打字。。。

HDU 1874：

#include <cstdio>#define MAXN 200#define INF 0xfffff int n;int Edge[MAXN][MAXN];int s[MAXN];int dist[MAXN];int path[MAXN];void Dijkstra(int v0) {int i, j, k;for (i = 0; i < n; i++) {dist[i] = Edge[v0][i];s[i] = 0;if (i != v0 && INF > dist[i])path[i] = v0;elsepath[i] = -1;}s[v0] = 1;dist[v0] = 0;for (i = 0; i < n - 1; i++) {int min = INF, u = v0;for (j = 0; j < n; j++)if (!s[j] && dist[j] < min){u = j;min = dist[j];}//ifs[u] = 1;for (k = 0; k < n; k++) {if (!s[k] && Edge[u][k] < INF && dist[u] + Edge[u] [k] < dist[k]) {dist[k] = dist[u] + Edge[u][k];path[k] = u;}//if}//for}//for}int main() {int m;int i, j;while (scanf("%d%d", &n, &m) && n && m) {for (i = 0; i < n; i++)for (j = 0; j < n; j++)if (i == j)Edge[i][j] = 0;elseEdge[i][j] = INF;int x, y, z;for (i = 0; i < m; i++) {scanf("%d%d%d", &x, &y, &z);if (z < Edge[x-1][y-1])Edge[y-1][x-1] = Edge[x-1][y-1] = z;}Dijkstra(0);printf("%d\n", dist[n - 1]);}//whilereturn 0;}