kuangbin_ShortPath G (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[][];

int n;

void spfa(int s)

{

    int dis[];

    bool vis[];

    memset(dis, 0x3f, sizeof dis);

    memset(vis, false, sizeof vis);

    queue<int> q;

    q.push(s);

    dis[s] = ;

    vis[s] = true;

    while(!q.empty()){

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = ; 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 = ;

    for(int i = ; i <= n; i++){

        ans = max(ans, dis[i]);

    }

    printf("%d\n", ans);

}

int main()

{

    scanf("%d", &n);

    for(int i = ; i <= n; i++){

        for(int j = ; j < i; j++){

            if(scanf("%d", &val[i][j]) == ){

                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();

    return ;

}