kuangbin_ShortPathG (POJ 1502)

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#define INF 0x3F3F3F3F
using namespace std;

int val[110][110];
int n;

void spfa(int s)
{
    int dis[110];
    bool vis[110];
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    vis[s] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = 1; i <= n; i++){
            if(u != i && dis[i] > dis[u] + val[u][i]){
                dis[i] = dis[u] + val[u][i];
                if(!vis[i]){
                    q.push(i);
                    vis[i] = true;
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, dis[i]);
    }
    printf("%d\n", ans);
}
int main()
{
    scanf("%d", &n);
    for(int i = 2; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(scanf("%d", &val[i][j]) == 1){
                val[j][i] = val[i][j];
            }
            else{
                getchar();
                val[i][j] = val[j][i] = INF;
            }
        }
    }
    /*output matrix
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            printf("%10d ", val[i][j]);
           putchar(‘\n‘);
    }*/
    spfa(1);
    return 0;
}