POJ – 2387 Til the Cows Come Home（Dijkstra堆优化）

Posted on | In , ,

思路：
最短路的裸题，不过想尝试一下以前没用过的Dijkstra的堆优化。Dijkstra的思路简单的说就是找目前没有扫描过的，且到出发点最近的点。标记其为使用过后再更新其周围的点的最短路径。常规时间复杂度为O(|V|^2)。在算法中我们可以使用一个小顶堆维护当前的离出发点最近的点，避免了多余的扫描，使得复杂度变为O(|E|log|V|)。这题一眼扫过去是个裸题就直接做了，没看到题目说可以有重边。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#define INF 1e9
#define ll long long
#define ms(a,val) memset(a,val,sizeof(a))
#define MOD 1000000007

using namespace std;
struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        if (a.first != b.first)return a.first < b.first;
        else return a.second < b.second;
    }
};
//如果要对结构体比较，在priority_queue第三个参数要传greater(from <functional>)或者一个拟函数，即如上的结构体，重载一个括号运算符.
const int MAXN = 1005,MAXV=2005;
int a[MAXN][MAXN], used[MAXN],line[MAXN];
priority_queue<pair<int,int>, vector<pair<int, int> >, cmp> pq;
void dijkstra(int N) {
    ms(used, 0);
    for (int i = 0;i < N;i++) line[i] = INF;
    line[N-1] = 0;
    pq.push(make_pair(0, N - 1));
    while(!pq.empty()) {
        pair<int,int> p = pq.top();
        pq.pop();
        int x = p.second, min = p.first;
        if (line[x] < min)continue;
        used[x] = 1;
        for (int j = 0;j < N;j++) {
            if (line[j] > line[x] + a[x][j]) {
                line[j]=line[x] + a[x][j];
                pq.push(make_pair(line[j], j));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T, N,f,t,l;
    while (cin >> T >> N) {
        for (int i = 0;i < N;i++) {
            for (int j = 0;j < N;j++) {
                a[i][j] = INF;
            }
        }
        for (int i = 0;i < T;i++) {
            cin >> f >> t >> l;
            if(a[f-1][t-1]>l)a[f-1][t-1] = l,a[t-1][f-1]=l;
        }
        dijkstra(N);
        cout << line[0]<<"\n";
        
    }
    return 0;
}