[kuangbin带你飞]专题四最短路练习

1. POJ2387 Til the Cows Come Home

题意：在一个无向图中，求点 n 到点 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
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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef pair<int, int> P;
typedef long long ll;
const int INF = 2e9, N = 1005, M = 4005;

int t, n, tot;
int ver[M], edge[M], Next[M], head[N], d[N], v[N];
priority_queue<P, vector<P>, greater<P> > q;

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}

void dijkstra() {
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    d[n] = 0;
    q.push(P(0, n));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push(P(d[y], y));
            }
        }
    }
}

int main() 
{
    scanf("%d%d", &t, &n);
    int x, y, z;
    while (t--) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    dijkstra();
    printf("%d\n", d[1]);
    return 0;
}

2. POJ2253 Frogger

题目链接

题意：湖中有 n 块石头，两只青蛙。在1号石头的 Freddy 蛙想去找在 2 号石头的 Fiona 蛙。青蛙距离指所有可能跳跃路径中在两块石头间跳跃距离最远的距离。求 1 号石头到 2 号石头所有可能路径中最小的青蛙距离。

可以 dijkstra，改变一下松弛方程即可，不知道为啥 G++ 要改成 float 才能过。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 2e9, N = 205;

struct Point {
    double x, y;
}p[N];

int n;
double d[N], mp[N][N];
int v[N];
priority_queue<P, vector<P>, greater<P> > q;

double dis(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) d[i] = INF;
    memset(v, 0, sizeof(v));
    d[s] = 0;
    q.push(P(0, s));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int i = 1; i <= n; ++i) {
            if (d[i] > max(d[x], mp[i][x])) {
                d[i] = max(d[x], mp[i][x]);
                q.push(P(d[i], i));
            }
        }
    }
}

int main() 
{
    int cnt = 0;
    while (scanf("%d", &n), n) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                mp[i][j] = mp[j][i] = dis(p[i], p[j]);
            }
        }
        dijkstra(1);
        printf("Scenario #%d\n", ++cnt);
        printf("Frog Distance = %.3lf\n\n", d[2]);
    }
    return 0;
}

3. POJ1787 Heavy Transportation

题目链接

题意：n 个点的无向图中，求 1 到 n 的所有路径中边最小值中最大的。

dijkstra + minmax，优先队列记得换成大根堆，否则会 T。

 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 <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 2e9, N = 1005, M = 1e6 + 5;

int t, n, m, tot;
int v[N], d[N];
int head[N], ver[M], edge[M], Next[M];
priority_queue<P, vector<P>, less<P> > q; // 大根堆

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}

void dijkstra(int s) {
    memset(v, 0, sizeof(v));
    q.push(P(INF, s));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i];
            if (d[y] < min(d[x], edge[i])) {
                d[y] = min(d[x], edge[i]);
                q.push(P(d[y], y));
            }
        }
    }
}

int main() 
{
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        memset(head, 0, sizeof(head));
        memset(d, 0, sizeof(d));
        d[1] = INF;
        tot = 0;
        scanf("%d%d", &n, &m);
        for (int j = 1; j <= m; ++j) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
            add(y, x, z);
        }
        dijkstra(1);
        printf("Scenario #%d:\n%d\n\n", i, d[n]);
    }
    return 0;
}

4. POJ3268 Silver Cow Party

题目链接

题意：n 个点 m 条边的有向图，奶牛从 a 到花费 t 时间，所有奶牛到奶牛 x 去参加聚会，聚会完后回到农场，求所有奶牛参加聚会并回来的最短时间的最大值。

先求x到各个农场的最小时间，再反向建图求x到各个农场的最小时间，二者之和的最大值即为答案。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 2e9, N = 1005, M = 1e5 + 5;

struct edge {
    int to, nxt, cost;
    edge() {}
    edge(int to, int nxt, int cost) : to(to), nxt(nxt), cost(cost) {}
}g[M], invg[M];

int n, m, x, tot;
int head[N], invhead[N], dis[N], invdis[N];

void add(int a, int b, int c) {
    g[++tot] = edge(b, head[a], c);
    head[a] = tot;
    invg[tot] = edge(a, invhead[b], c);
    invhead[b] = tot;
}

void dijkstra(edge (&G)[M], int (&d)[N], int (&h)[N]) {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(d, 0x3f, sizeof(d));
    d[x] = 0;
    q.push(P(0, x));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        for (int i = h[x]; i; i = G[i].nxt) {
            int y = G[i].to;
            if (d[y] > d[x] + G[i].cost) {
                d[y] = d[x] + G[i].cost;
                q.push(P(d[y], y));
            }
        }
    }
}

int main() 
{
    scanf("%d%d%d", &n, &m, &x);
    int a, b, c;
    while (m--) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    dijkstra(g, dis, head);
    dijkstra(invg, invdis, invhead);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dis[i] + invdis[i]);
    }
    printf("%d\n", ans);
    return 0;
}

5. POJ1860 Currency Exchange

题目链接

题意：N 种货币，M 个交换点，每个交换点只能交换 2 种货币，交换公式为 (now - c) * r，其中 c($0\le c\le10^2$)为税款，r($10^{-2}\le r\le10^2$)为汇率，Nick 有第 S 种货币，V 本金，问能否经过若干次交换后使价值增加。

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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 105, M = 205;

int n, m, s, tot;
double v;
int head[N], vis[N], cnt[N];
int ver[M], nxt[M];
double d[N], co[M], rate[M];

void add(int x, int y, double r, double c) {
    ver[++tot] = y, co[tot] = c, rate[tot] = r, nxt[tot] = head[x], head[x] = tot;
}

void spfa() {
    queue<int> q;
    vis[s] = 1;
    cnt[s] = 1;
    d[s] = v;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] < (d[x] - co[i]) * rate[i]) {
                d[y] = (d[x] - co[i]) * rate[i];
                if (!vis[y]) {
                    q.push(y);
                    vis[y] = 1;
                    if(++cnt[y] == n) {
                        puts("YES");
                        return;
                    }
                }
            }
        }
    }
    puts("NO");
}

int main() 
{
    scanf("%d%d%d%lf", &n, &m, &s, &v);
    int x, y;
    double r1, c1, r2, c2;
    while (m--) {
        scanf("%d%d%lf%lf%lf%lf", &x, &y, &r1, &c1, &r2, &c2);
        add(x, y, r1, c1);
        add(y, x, r2, c2);
    }
    spfa();
    return 0;
}

6. POJ3259 Wormholes

题目链接

题意：F 个农场，N 块田地，M 个双向路径，W 个虫洞(单向路径)，虫洞是时光倒流路径，农夫 Jorn 想知道能否遇到以前的自己。

下面默认 1 为源点，用 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
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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9;
const int N = 505, M = 5205;

int t, n, m, w, tot;
int d[N], v[N], cnt[N];
int head[N], ver[M], edge[M], nxt[M];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void spfa() {
    queue<int> q;
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    memset(cnt, 0, sizeof(cnt));
    d[1] = 0;
    cnt[1] = 1;
    v[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        v[x] = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                if (!v[y]) {
                    q.push(y);
                    v[y] = 1;
                    if (++cnt[y] == n) {
                        puts("YES");
                        return;
                    }
                }
            }
        }
    }
    puts("NO");
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &w);
        int x, y, z;
        tot = 0;
        memset(head, 0, sizeof(head));
        while (m--) {
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
            add(y, x, z);
        }
        while (w--) {
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, -z);
        }
        spfa();
    }
    return 0;
}

若测试数据有非连通图，我们用 floyd 判断负权勉强可以过。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 505;

int t, n, m, w;
int d[N][N];

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (d[i][j] > d[i][k] + d[k][j])
                    d[i][j] = d[i][k] + d[k][j]; // 用min会T
            }
            if (d[i][i] < 0) {
                puts("YES");
                return;
            }
        }
    }
    puts("NO");
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &w);
        memset(d, 0x3f, sizeof(d));
        for (int i = 1; i <= n; ++i) d[i][i] = 0;
        int x, y, z;
        while (m--) {
            scanf("%d%d%d", &x, &y, &z);
            if (z < d[x][y])
                d[x][y] = d[y][x] = z;
        }
        while (w--) {
            scanf("%d%d%d", &x, &y, &z);
            d[x][y] = -z;
        }
        floyd();
    }
    return 0;
}

7. POJ1502 MPI Maelstrom

题目链接

题意：n 个处理器，第一个处理器给另一个处理器发送信息后，两个处理器可以同时给其他连接的处理器发送信息，但信息不一定同时到达，给出$n\times n$的邻接矩阵，A(i,j)表示处理器 i 到 j 的通信时间，网络是无向的即 A(i,j)=A(j,i)，处理器发送信息到自身不需要网络通信即 A(i,i)=0，因此只给出下三角矩阵，求第一个处理器广播信息到其他所有处理器的最短时间。

dijkstra 裸题，神奇的 POJ 用 stoi 会 CE。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <string>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 2e9, N = 105;

int n;
int mp[N][N], d[N], v[N];

void dijkstra() {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int y = 1; y <= n; ++y) {
            if (d[y] > d[x] + mp[x][y]) {
                d[y] = d[x] + mp[x][y];
                q.push(P(d[y], y));
            }
        }

    }
}

int main() 
{
    scanf("%d", &n);
    string s;
    memset(mp, 0x3f, sizeof(mp));
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            cin >> s;
            if (s != "x") mp[i][j] = mp[j][i] = atoi(s.c_str());
        }
    }
    dijkstra();
    int ans = 0;
    for (int i = 2; i <= n; ++i)
        ans = max(ans, d[i]);
    printf("%d\n", ans);
    return 0;
}

8. POJ3660 Cow Contest

题目链接

题意：n 头牛程序竞赛，如果 A 拥有比 B 更高的技术水平，那么 A 将永远打败 B，给定 M 场比赛的结果，问有多少牛排名可以确定。

用floyd传递闭包，若一个牛和其余牛关系确定，则该牛排名确定。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 105;

int n, m;
int win[N][N];

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j= 1; j <= n; ++j) {
                win[i][j] |= win[i][k] & win[k][j];
            }
        }
    }
}

int main() 
{
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        win[a][b] = 1;
    }
    floyd();
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int flag = 0;
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            if (!win[i][j] && !win[j][i]) {
                flag = 1;
                break;
            }
        }
        if (!flag) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

9. POJ2240 Arbitrage

题目链接

题意：给定 n 种货币，m 种货币汇率，问是否存在一种套利方式，使 1 单位的货币变成比 1 单位更多的同种货币。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <string>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 2e9, N = 35;
const double eps = 1e-8;

int n, m;
map<string, int> mp;
double d[N][N];

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                d[i][j] = max(d[i][j], d[i][k] * d[k][j]);
            }
            if (d[i][i] - 1 > eps) {
                puts("Yes");
                return;
            }
        }
    }
    puts("No");
}

int main() 
{
    int cnt = 0;
    while (scanf("%d", &n), n) {
        mp.clear();
        string s;
        for (int i = 1; i <= n; ++i) {
            cin >> s;
            mp[s] = i;
            d[i][i] = 1;
        }
        scanf("%d", &m);
        string cur1, cur2;
        double rate;
        for (int i = 1; i <= m; ++i) {
            cin >> cur1 >> rate >> cur2;
            d[mp[cur1]][mp[cur2]] = rate;
        }
        printf("Case %d: ", ++cnt);
        floyd();
    }
    return 0;
}

10. POJ1511 Invitation Cards

题目链接

题意：给定 n 个点和 m 个单向路径，求 1 号点到其他点的最短路及其他点到 1 号点的最短路之和。

dijkstra(2219ms)，可以用快读加下速。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<ll, int> P;
const ll INF = 1e18;
const int N = 1e6 + 5, M = 2e6 + 5;

int t, n, m, tot;
ll dis[N], rdis[N];
int head[N], rhead[N];
int ver[M], edge[M], nxt[M], vis[N];

void add(int (&h)[N], int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = h[x], h[x] = tot;
}

void dijkstra(ll (&d)[N], int (&h)[N]) {
    priority_queue<P, vector<P>, greater<P> > q;
    for (int i = 1; i <= n; ++i) d[i] = INF;
    memset(vis, 0, sizeof(vis));
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = h[x]; i; i = nxt[i]) {
            int y = ver[i];
            ll z = d[x] + (ll)edge[i];
            if (d[y] > z) {
                d[y] = z;
                q.push(P(d[y], y));
            }
        }
    }
}

int main() 
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        memset(head, 0, sizeof(head));
        memset(rhead, 0, sizeof(rhead));
        int x, y, z;
        tot = 0;
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &x, &y, &z);
            add(head, x, y, z);
            add(rhead, y, x, z);
        }
        dijkstra(dis, head);
        dijkstra(rdis, rhead);
        ll ans = 0;
        for (int i = 1; i <= n; ++i) ans += dis[i] + rdis[i];
        printf("%lld\n", ans);
    }
    return 0;
}

11. POJ3159 Candies

题目链接

题意：n 个人分糖果，m 个约束条件$(a,b,c)$表示b的糖果不能比 a 多 c 个以上，即$d[a]+c\ge d[b]$，求 1 比 n 少的最大糖果差异数。

差分约束系统问题，图中有负边则必须使用 Bellman-Ford 算法，$d[a]+c\ge d[b]$，可以视为从 a 到 b 连一条长度为 c 的有向边，转化为求 1 到 n 的最短路。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 2e9, N = 3e4 + 5, M = 15e4+5;

int n, m, tot;
int d[N], head[N], vis[N];
int ver[M], edge[M], nxt[M];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void dijkstra() {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                q.push(P(d[y], y));
            }
        }
    }
}

int main() 
{
    scanf("%d%d", &n, &m);
    int x, y, z;
    while (m--) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra();
    printf("%d\n", d[n]);
    return 0;
}

12. POJ2502 Subway

题目链接

题意：从家去学校，步行速度$10km/h$，地铁速度$40km/h$，给定家和学校的坐标，以及若干条地铁线路地铁站坐标，求家到学校的最少时间。

根据题意见图跑最短路即可。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<double, int> P;
const int N = 205, M = 1e5 + 5;
const double INF = 1e18;

struct point {
    int x, y;
    point() {}
    point(int x, int y) : x(x), y (y) {}
}p[N];

int cnt, tot;
double d[N], edge[M];
int vis[N], head[N];
int ver[M], nxt[M];

double getdis(point a, point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void add(int x, int y, double z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void dijkstra() {
    priority_queue<P, vector<P>, greater<P> > q;
    for (int i = 1; i <= cnt; ++i) d[i] = INF;
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                q.push(P(d[y], y));
            }
        }
    }
}

int main() 
{
    int sx, sy, ex, ey;
    scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
    p[++cnt] = point(sx, sy);
    int x, y;
    while (~scanf("%d%d", &x, &y)) {
        p[++cnt] = point(x, y);
        while (scanf("%d%d", &x, &y), x + 1) {
            p[++cnt] = point(x, y);
            double dis = getdis(p[cnt-1], p[cnt]) * 60.0 / 40000;
            add(cnt - 1, cnt, dis);
            add(cnt, cnt - 1, dis);
        }
    }
    p[++cnt] = point(ex, ey);
    for (int i = 1; i < cnt; ++i) {
        for (int j = i + 1; j <= cnt; ++j) {
            double dis = getdis(p[i], p[j]) * 60.0 / 10000;
            add(i, j, dis);
            add(j, i, dis);
        }
    }
    dijkstra();
    printf("%d\n", int(d[cnt] + 0.5));
    return 0;
}

13. POJ1062 昂贵的聘礼

题目链接

题意：N 件物品，每件物品价格 P，主人地位等级 L，替代品总数X，两人地位等级差超过 M 不能间接交易，求 1 号物品的最少价格。

以 0 为源点，物品所需的金币数为权值见图，问题即求 d[1]，酋长等级 l[1]，枚举以$l[1]-m\to l[1]$为最小等级长度为 m 的区间求最短路即可。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int ,int> P;
const int INF = 2e9, N = 105, M = 1e4 + 5;

int m, n, p, x, tot, level;
int d[N], head[N], l[N], vis[N];
int ver[M], edge[M], nxt[M];

void add(int u, int v, int w) {
    ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}

void dijkstra() {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    d[0] = 0;
    q.push(P(0 ,0));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = nxt[i]) {
            int v = ver[i];
            if (l[v] < level || l[v] > level + m) continue;
            if (d[v] > d[u] + edge[i]) {
                d[v] = d[u] + edge[i];
                q.push(P(d[v], v));
            }
        }
    }
}

int main() 
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &p, &l[i], &x);
        add(0, i, p);
        int u, v;
        while (x--) {
            scanf("%d%d", &u, &v);
            add(u, i, v);
        }
    }
    int ans = INF;
    for (level = l[1] - m; level <= l[1]; ++level) {
        dijkstra();
        ans = min(ans, d[1]);
    }
    printf("%d\n", ans);
    return 0;
}

14. POJ1847 Tram

题目链接

题意：n 个路口，每个路口通向多条路，默认向第 1 条路口，轨道通向其他路口需要转换一次开关，求路口 A 到路口 B 所需的最小转换次数。

通向默认路口权值为 0，转换一次开关为 1 建图。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 105;

int n, a, b, t, y;
int g[N][N];

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j)  {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}

int main() 
{
    memset(g, 0x3f, sizeof(g));
    scanf("%d%d%d", &n, &a, &b);
    for (int x = 1; x <= n; ++x) {
        scanf("%d", &t);
        for (int j = 1; j <= t; ++j) {
            scanf("%d", &y);
            if (j == 1) g[x][y] = 0;
            else g[x][y] = 1;
        }
    }
    floyd();
    if (g[a][b] == INF) puts("-1");
    else printf("%d\n", g[a][b]);
    return 0;
}

15. LightOJ1074 Extended Traffic

题目链接

题意：n 个交叉路口，每个路口有拥挤度$a_i$，旅行者从路口 i 到 j 城市管理者获得$(a_j-a_i)^3$的费用，求 0 号路口到其他路口的最少费用。

可能存在负环，用 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
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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 205, M = 2e4 + 5;

int t, n, m, q, tot;
int a[N], vis[N], d[N], cnt[N], head[N], cir[N];
int ver[M], edge[M], nxt[M];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void dfs(int x) {
    cir[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (!cir[x]) dfs(y);
    }
}

void spfa() {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memset(cnt, 0, sizeof(cnt));
    memset(cir, 0, sizeof(cir));
    d[1] = 0;
    vis[1] = 1;
    cnt[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (cir[y]) continue;
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                if (!vis[y]) {
                    vis[y] = 1;
                    q.push(y);
                    if (++cnt[y] >= n) dfs(y);
                }
            }
        }
    }
}

int main() 
{
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        memset(head, 0, sizeof(head));
        scanf("%d", &n);
        for (int j = 1; j <= n; ++j) scanf("%d", &a[j]);
        scanf("%d", &m);
        int x, y;
        tot = 0;
        while (m--) {
            scanf("%d%d", &x, &y);
            add(x, y, (a[y] - a[x]) * (a[y] - a[x]) * (a[y] - a[x]));
        }
        spfa();
        printf("Case %d:\n", i);
        scanf("%d", &q);
        while (q--) {
            scanf("%d", &x);
            if (cir[x] || d[x] < 3 || d[x] == INF) puts("?");
            else printf("%d\n", d[x]);
        }
        
    }
    return 0;
}

16. HDU4725 The Shortest Path in Nya Graph

题目链接

题意：n 个点，每个点都属于一个层 l，相邻两层距离为 c，另外给出 m 条无向边，求点 1 到点 n 的最短路。

利用拆点的思想，相邻两层所有点连边复杂度高，将每一层视为一个点，由于同层的点不一定连通，每层拆为入点出点两个点，不妨设$n+1\sim3n$中奇数号为出点偶数号为入点，每层内的点连分别连至出入点，相邻两层出入点相连接。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 3e5 + 5, M = 6e5 + 5;

int t, n, m, c, tot;
int d[N], vis[N], head[N];
int ver[M], edge[M], nxt[M];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void dijkstra() {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    q.push(P(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                q.push(P(d[y], y));
            }
        }
    }
}

int main() 
{
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        memset(head, 0, sizeof(head));
        tot = 0;
        scanf("%d%d%d", &n, &m, &c);
        int x, y, z;
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &x);
            add(j, n + 2 * x - 1, 0);
            add(n + 2 * x, j, 0);
        }
        for (int j = 1; j <= n; ++j) {
            add(n + 2 * j - 1, n + 2 * (j + 1), c);
            add(n + 2 * j + 1, n + 2 * j, c);
        }
        for (int j = 1; j <= m; ++j) {
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
            add(y, x, z);
        }
        dijkstra();
        printf("Case #%d: ", i);
        if (d[n] == INF) puts("-1");
        else printf("%d\n", d[n]);
    }
    return 0;
}

17. HDU3416 Marriage Match IV

题目链接

题意：。

18. HDU4370 0 or 1

题目链接

题意：给出一个$n\times n$的矩阵$c_{i,j}$，找出一个$n\times n$的 0-1 矩阵$x_{i,j}$满足

$x_{1,2}+x_{1,3}+\cdots+x_{1,n}=1$
$x_{1,n}+x_{2,n}+\cdots+x_{n-1,n}=1$
$\displaystyle\sum x_{k,i}(1\le k\le n)=\sum x_{i,j}(1\le j\le n).\quad(1\lt i\lt n)$

使得$\displaystyle\sum c_{i,j}*x_{i,j}(1\le i,j\le n)$最小，求这个最小值。

条件 1：1 号结点出度为 1，且不指向自身；条件 2：n 号结点入度为 1，发出者不是自身；条件 3：$2\sim n-1$的每个结点出度等于入度。原问题可以转化为两种情况，1. 结点 1 最终指向 n，求从 1 号结点到 n 号结点的最短路 d[n]。2. 结点 1 形成自环，则结点 n 也必然形成自环，求 d[1] + d[n]，d[1] 以 1 为起点，d[n] 以 n 为起点。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 305;

int n;
int d[N], vis[N], c[N][N];

void spfa(int s) {
    queue<int> q;
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i) {
        if (i == s) continue;
        d[i] = c[s][i];
        q.push(i);
        vis[i] = 1;
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = 1; i <= n; ++i) {
            if (d[i] > d[x] + c[x][i]) {
                d[i] = d[x] + c[x][i];
                if (!vis[i]) q.push(i), vis[i] = 1;
            }
        }
    }	
}

int main() 
{
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                scanf("%d", &c[i][j]);
            }
        }
        spfa(1);
        int ans = d[n];
        int d1 = d[1];
        spfa(n);
        int d2 = d[n];
        printf("%d\n", min(ans, d1 + d2));
    }
    
    return 0;
}

19. POJ3169 Layout

题目链接

题意：n 头奶牛在一条直线上按编号排列，ml 对奶牛关系好，进食的距离不能超过某值，md 对奶牛关系不好，进食的距离不能小于某值，满足条件的排列中，求 1 号牛和 n 号牛的最大距离，若没有的排列输出 -1，1 号和 n 号距离无穷大输出 -2。

一道差分约束系统问题，i 号牛位置为$d[i]$，$d[i]$单调递增，对关系好的$(x,y,z)$，$d[y]\le d[x]+z$，视为从 x 到 y 连一条长度为 z 的有向边；对关系不好的$(x,y,z)$，$d[x]+z\le d[y]$，视为从 y 到 x 连一条长度 -z 的有向边，$d[n]-d[1]$的最大值即 1 到 n 的最短路。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005, M = 2e4 + 5;

int n, ml, md, tot;
int d[N], vis[N], head[N], cnt[N];
int ver[M], edge[M], nxt[M];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void spfa() {
    queue<int> q;
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    vis[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                if (!vis[y]) {
                    vis[y] = 1;
                    q.push(y);
                    if (++cnt[y] >= n) {
                        puts("-1");
                        return;
                    }
                }
            }
        }
    }
    if (d[n] == INF) puts("-2");
    else printf("%d\n", d[n]);
}

int main() 
{
    scanf("%d%d%d", &n, &ml, &md);
    int x, y, z;
    while (ml--) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    while (md--) {
        scanf("%d%d%d", &x, &y, &z);
        add(y, x, -z);
    }
    spfa();
    return 0;
}

Contents

1. POJ2387 Til the Cows Come Home

2. POJ2253 Frogger

3. POJ1787 Heavy Transportation

4. POJ3268 Silver Cow Party

5. POJ1860 Currency Exchange

6. POJ3259 Wormholes

7. POJ1502 MPI Maelstrom

8. POJ3660 Cow Contest

9. POJ2240 Arbitrage

10. POJ1511 Invitation Cards

11. POJ3159 Candies

12. POJ2502 Subway

13. POJ1062 昂贵的聘礼

14. POJ1847 Tram

15. LightOJ1074 Extended Traffic

16. HDU4725 The Shortest Path in Nya Graph

17. HDU3416 Marriage Match IV

18. HDU4370 0 or 1

19. POJ3169 Layout