hdu1874 – 暢通工程續

Problem Description

某省自從實行了很多年的暢通工程計劃後，終于修建了很多路。不過路多了也不好，每次要從一個城鎮到另一個城鎮時，都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。

現在，已知起點和終點，請你計算出要從起點到終點，最短需要行走多少距離。

Input

本題目包含多組資料，請處理到檔案結束。

每組資料第一行包含兩個正整數N和M(0<N<200,0<M<1000)，分别代表現有城鎮的數目和已修建的道路的數目。城鎮分别以0～N-1編号。

接下來是M行道路資訊。每一行有三個整數A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮A和城鎮B之間有一條長度為X的雙向道路。

再接下一行有兩個整數S,T(0<=S,T<N)，分别代表起點和終點。

Output

對于每組資料，請在一行裡輸出最短需要行走的距離。如果不存在從S到T的路線，就輸出-1.

Sample Input

3 3

0 1 1

0 2 3

1 2 1

0 2

3 1

0 1 1

1 2

Sample Output

2

-1

最短路，迪傑斯特拉算法，O（ElogV）

ac代碼：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

typedef pair<int, int> P;//first最短距離, second頂點編号
struct edge{
    int to;
    int cost;
};
vector<edge> G[1000];
void add(int x, int y, int z){//無向圖
    edge e;
    e.to = y;
    e.cost = z;
    G[x].push_back(e);
    e.to = x;
    e.cost = z;
    G[y].push_back(e);
}
int n, m;
int s, t;
int d[1000];//最短路
void dijsktra(int s){
    priority_queue<P, vector<P>, greater<P> > que;
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    que.push(P(0, s));
    while(!que.empty()){
        P p = que.top();
        que.pop();
        //cout << p.first << ' ' << p.second << endl;
        int v = p.second;
        if(d[v] < p.first) continue;
        for(int i = 0; i < G[v].size(); i++){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
    if(d[t] != 0x3f3f3f3f)printf("%d\n", d[t]);
    else printf("-1\n");
    for(int i = 0; i < 1000; i++) G[i].clear();
}
int main(){
    int a, b, c;
    while(~scanf("%d %d", &n, &m)){
        for(int i = 0; i < m; i++){
            scanf("%d %d %d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d %d", &s, &t);
        dijsktra(s);
    }
    return 0;
}