POJ1502 MPI Maelstrom Dijkstra

POJ1502 MPI Maelstrom Dijkstra

題意

給出圖，從點1出發，求到最後一個點的時間。

思路

單源最短路，沒什麼好說的。注意讀入的時候的技巧。

代碼

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 1000000000;
const int maxn = 110;
int n;
int edge[maxn][maxn];
int d[maxn];
bool used[maxn];
void dijkstra(int s)
{
    d[s] = 0;
    while(true) {
        int v = -1;
        for(int i = 1 ; i <= n ; i ++) {
            if(!used[i]) {
                if(v == -1 || d[i] < d[v]) v = i;
            }
        }
        if(v == -1) break;
        used[v] = true;
        for(int i = 1 ; i <= n ; i ++) {
            d[i] = min(d[i],d[v]+edge[v][i]);
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    fill(d,d+maxn,INF);
    memset(used,false,sizeof(used));
    for(int i = 0 ; i < maxn ; i ++) {
        fill(edge[i],edge[i]+maxn,INF);
        edge[i][i] = 0;
    }
    scanf("%d",&n);
    for(int i = 2 ; i <= n ; i ++) {
        for(int j = 1 ; j < i ; j ++) {
            int tmp;
            char getit;
            if(scanf("%d",&tmp))
                edge[i][j] = edge[j][i] = tmp;
            else scanf("%c",&getit);
        }
    }
    dijkstra(1);
    int ma = d[1];
    for(int i = 2 ; i <= n ; i ++) {
        ma = max(d[i],ma);
    }
    cout << ma << endl;
    return 0;
}