HDU1874 – 畅通工程续

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87



#include <bits/stdc++.h>
#define CLR(x) memset((x), 0, sizeof(x))
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)+1)
#ifndef LCYTEST
#   define release(_x) { _x }
#else
#   define release(_x) ;
#endif
using namespace std;
const int ESIZ = 1E5;

struct tgno {
    int u, v, w;
    tgno* n;
} POOL[ESIZ]; int ppos;
tgno* Head[ESIZ];
int N, M;

void mkGraph() { CLR(POOL), CLR(Head); }
void _add(int u, int v, int w) {
    POOL[ppos].u = u; POOL[ppos].v = v;
    POOL[ppos].w = w; POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}
void addEdge(int u, int v, int w) { _add(u, v, w); _add(v, u, w); }

struct zkwheap {
    int mmin[ESIZ];
    int mark[ESIZ];
    int cap; int M;

    void mkTree(int c) {
        cap = c;
        memset(mmin, 0x3F, sizeof(mmin));
        memset(mark, 0, sizeof(mark));
        for(M=1;M<cap;M<<=1);
        for(int i=0;i<cap;i++) mark[M+i] = i+1;
    }

    void fix(int cur) {
        cur>>=1;
        for(;cur;cur>>=1) {
            mmin[cur] = min(mmin[lson(cur)], mmin[rson(cur)]);
            mark[cur] = (mmin[cur]==mmin[lson(cur)])?mark[lson(cur)]:mark[rson(cur)];
        }
    }
    int top() { return mmin[1]; }
    int top_pos() { return mark[1]; }
    void pop() { mmin[M-1+mark[1]] = 0x3F3F3F3F; fix(M-1+mark[1]); }
    void change(int k, int v) { mmin[M-1+k] = v; fix(M-1+k); }
};

int dis[ESIZ]; zkwheap Q;
void Dijkstra(int S, int T) {
    memset(dis, 0x3F, sizeof(dis));
    Q.mkTree(N);
    Q.change(S, 0); dis[S] = 0;
    for(int i=1;i<N;i++) {
        int cur = Q.top_pos();
        dis[cur] = Q.top(); Q.pop();
        if(cur == T) return;
        typedef tgno* It;
        for(It i=Head[cur];i;i=i->n) {
            if(dis[i->v] > dis[cur] + i->w) {
                dis[i->v] = dis[cur] + i->w;
                Q.change(i->v, dis[i->v]);
            }
        }
    }
}

int main() {
    release({ ios::sync_with_stdio(false); cin.tie(NULL); });
    while(cin >> N >> M) {
        mkGraph();
        int u, v, w;
        for(int i=0;i<M;i++) {
            cin >> u >> v >> w; ++u, ++v; // u, v (= [1, N]
            addEdge(u, v, w);
        }

        int S, T; cin >> S >> T; ++S, ++T;
        Dijkstra(S, T);
        cout << (dis[T] == 0x3F3F3F3F ? -1 : dis[T]) << endl;
    }
}