程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ1502 MPI Maelstrom Dijkstra

POJ1502 MPI Maelstrom Dijkstra

編輯:C++入門知識

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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved