HOJ 1874 畅通工程续（单源最短路径dijkstra，水题）

单源最短路径dijkstra，水题
本题要点：
1、n <= 200, 直接用邻接矩阵存图，重边的话取最小值。套用 dijkstra 模板。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 210;
int n, m, s, t;
int a[MaxN][MaxN], d[MaxN];
bool vis[MaxN];void dijkstra()
{
    memset(d, 0x3f, sizeof d);memset(vis, false, sizeof vis);d[s] = 0;for(int i = 1; i < n; ++i)	// 重复 n - 1 次{
    int x = -1;for(int j = 0; j < n; ++j){
    if(!vis[j] && (-1 == x || d[j] < d[x]))x = j;}if(-1 == x)return;vis[x] = 1;// 利用 全局最小值点x更新其他值for(int y = 0; y < n; ++y){
    d[y] = min(d[y], d[x] + a[x][y]);}}
}int main()
{
    int x, y, z;while(scanf("%d%d", &n, &m) != EOF){
    memset(a, 0x3f, sizeof a);for(int i = 0; i < n; ++i){
    a[i][i] = 0;}for(int i = 0; i < m; ++i){
    scanf("%d%d%d", &x, &y, &z);a[x][y] = min(a[x][y], z);a[y][x] = min(a[y][x], z);}scanf("%d%d", &s, &t);dijkstra();if(d[t] == 0x3f3f3f3f){
    printf("-1\n");}else{
    printf("%d\n", d[t]);	}}return 0;
}/* 3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2 *//* 2 -1 */