POJ - 1502MPI Maelstrom

BIT has recently taken delivery of their new supercomputer, a 32 processor Apollo Odyssey distributed shared memory machine with a hierarchical communication subsystem. Valentine McKee’s research advisor, Jack Swigert, has asked her to benchmark the new system.

求源點到所有點最短距離中的最長距離，spfa解決。

#include<iostream>
#include<queue>
#include<math.h>
#include<stdio.h>
#include<string>
using namespace std;
#define N 6000+5
#define LL long long int
#define pow(a) ((a)*(a))
#define INF 0x3f3f3f3f
#define mem(arr,a) memset(arr,a,sizeof(arr))
struct edge{
    int to;
    int cost;
};

int d[N];
int used[N];
int num[N];
int V, E = ;
vector<edge> e[N];
bool spfa(int s){
    mem(d, INF);
    mem(num, );
    d[s] = ;
    queue<int>q;
    q.push(s);
    while (!q.empty()){
        int x = q.front(); q.pop();
        for (int i = ; i < e[x].size(); i++){
            edge temp = e[x][i];
            int t = temp.to;
            if (d[t]>d[x] + temp.cost){
                d[t] = d[x] + temp.cost;
                q.push(t);
                num[t]++;
                if (num[t] == V){
                    return false;
                }
            }
        }
    }
    return true;
}
int main(){
    cin >> V;
    for (int i = ; i <= V; i++){
        for (int j = ; j < i; j++){
            edge es;
            string cost; cin >> cost;
            if (cost[] == 'x'){
                j += cost.size() - ;
                continue;
            }
            else
            {
                es.to = j; es.cost = atoi(cost.c_str());
                e[i].push_back(es);
                es.to = i;
                e[j].push_back(es);
            }
        }
    }
    int MAX = ;
    if (spfa()){
        for (int i = ; i <= V; i++){
            MAX = max(MAX, d[i]);
        }
        cout << MAX << endl;
    }
    else{
        cout << "NO" << endl;
    }
}