P2865 [USACO06NOV]Roadblocks G

1. Dijkstra

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
int dis[MAXn + 10], secdis[MAXn + 10];
priority_queue<pair<int, int> > q;
void Dijkstra(int root) {
    memset(dis, 0x3f, sizeof(dis));
    memset(secdis, 0x3f, sizeof(secdis));
    dis[root] = 0;
    q.push(make_pair(0, root));
    while (!q.empty()) {
        int cur = q.top().second, d = -q.top().first; q.pop();
        if (secdis[cur] < d) continue;
        for (re int i = head[cur]; i; i = nex[i]) {
            int dist = d + wei[i];
            if (dis[to[i]] > dist) {
                swap(dis[to[i]], dist);
                q.push(make_pair(-dis[to[i]], to[i]));
            }
            if (secdis[to[i]] > dist) {
                secdis[tod[i]] = dist;
                q.push(make_pair(-secdis[to[i]], to[i]));
            }
        }
    }
}

// main函数中
Dijkstra(root);
printf("%d\n", secdis[cur]);

2. Spfa

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
int secdis[MAXn + 10], dis[MAXn + 10];
bool inque[MAXn + 10];
queue<int> q;
int tmp[4];
bool update(int &dis1, int &secdis1, int dis2, int secdis2) {
    tmp[0] = dis1, tmp[1] = secdis1, tmp[2] = dis2, tmp[3] = secdis2;
    sort(tmp, tmp + 4);
    unique(tmp, tmp + 4);
    if (dis1 != tmp[0] || secdis1 != tmp[1]) {
        dis1 = tmp[0], secdis1 = tmp[1];
        return 1;
    } else {
        return 0;
    }
}
void Spfa(int sour) {
    memset(secdis, 0x3f, sizeof(secdis));
    memset(dis, 0x3f, sizeof(dis));
    dis[sour] = 0;
    q.push(sour); inque[sour] = 1;
    while (!q.empty()) {
        int cur = q.front(); q.pop(); inque[cur] = 0;
        for (int i = head[cur]; i; i = nex[i]) {
            if (update(dis[to[i]], secdis[to[i]], dis[cur] + wei[i], secdis[cur] + wei[i])) {
                if (!inque[to[i]]) {
                    q.push(to[i]); inque[to[i]] = 1;
                }
            }
        }
    }
}

// main函数中
Spfa(root);
printf("%d\n", secdis[cur]);