kuangbin 专题四 最短路练习

Posted on Edited on In

题目详单见 [kuangbin带你飞]专题1-23。
算法介绍见 最短路 - OI Wiki。

POJ-2387 Til the Cows Come Home

求最短路，方法参见 最短路 - OI Wiki。

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>
using namespace std;
const int N = 1001, M = 4002;
int t, n, ans = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
void add(int u, int v, int ww)
{
    e[++idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx;
}
void dfs(int u, int c)
{
    if (c >= ans)
        return;
    if (u == 1)
    {
        ans = c;
        return;
    }
    for (int i = h[u]; i; i = ne[i])
    {
        int v = e[i];
        if (st[v])
            continue;
        st[v] = 1;
        dfs(v, c + w[i]);
        st[v] = 0;
    }
}
int main()
{
    cin >> t >> n;
    for (int i = 0, a, b, c; i < t; ++i)
    {
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    st[n] = 1;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}
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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1001, M = 4002;
int t, n, ans = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
struct node
{
    int d, u;
    bool operator>(const node &a) const { return d > a.d; }
};
priority_queue<node, vector<node>, greater<node> > q;
void add(int u, int v, int ww)
{
    e[++idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx;
}
void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[n] = 0;
    q.push({0, n});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (int i = h[u]; i; i = ne[i])
        {
            int v = e[i];
            if (dist[v] > dist[u] + w[i])
                q.push({dist[v] = dist[u] + w[i], v});
        }
    }
}
int main()
{
    cin >> t >> n;
    for (int i = 0, a, b, c; i < t; ++i)
    {
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    dijkstra();
    cout << dist[1] << endl;
    return 0;
}

POJ-2253 Frogger

极小化极大值，可以用最短路算法，需改更改松弛操作函数，从经典的 f[x][y] = min(f[x][y], f[x][k]+f[k][y]) 转为 f[i][j] = min(f[i][j], max(f[i][k], f[k][j]))。本题也可以用最小生成树算法。需要注意初始值大小，以及比较函数，与下一题相映照。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 201;
int t, n, x[N], y[N];
double dist[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)
                dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));
}
int main()
{
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; ++i)
            cin >> x[i] >> y[i];

        memset(dist, 0, sizeof dist);
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                dist[i][j] = dist[j][i] = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
        floyd();
        printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++t, dist[1][2]);
    }
    return 0;
}
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int N = 201;
int t, n, x[N], y[N];
double g[N][N], dist[N];
bool st[N];
struct node
{
    double w;
    int u;
    bool operator>(const node &a) const { return w > a.w; }
};
void dijkstra()
{
    priority_queue<node, vector<node>, greater<node> > q;
    fill(dist, dist + N, 1e3);
    memset(st, 0, sizeof st);
    dist[1] = 0;
    q.push({0, 1});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (int v = 1; v <= n; ++v)
            if (dist[v] > max(dist[u], g[u][v]))
                q.push({dist[v] = max(dist[u], g[u][v]), v});
    }
}
int main()
{
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; ++i)
            cin >> x[i] >> y[i];

        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                g[i][j] = g[j][i] = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
        dijkstra();
        printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++t, dist[2]);
    }
    return 0;
}
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 201;
int t, n, m, x[N], y[N], p[N];
double get_dist(int i, int j)
{
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
struct edge
{
    double w;
    int u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
void kruskal()
{
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b)
            p[a] = b;
        if (find(1) == find(2))
        {
            printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++t, e[i].w);
            break;
        }
    }
}
int main()
{
    while (cin >> n, n)
    {
        m = 0;
        for (int i = 1; i <= n; ++i)
            cin >> x[i] >> y[i];
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j < i; ++j)
                e[m++] = {get_dist(i, j), i, j};
        kruskal();
    }
    return 0;
}

POJ-1797 Heavy Transportation

同上题，不过是反方向（极大化极小值）。此外，数据量较大不适合用 Floyd。稠密图，更适合用 Prim 而非 Kruskal。

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
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1001;
int t, n, m, g[N][N], dist[N];
bool st[N];
struct node
{
    int w, u;
    bool operator<(const node &a) const { return w < a.w; }
};
void dijkstra()
{
    priority_queue<node> q;
    memset(dist, 0, sizeof dist);
    memset(st, 0, sizeof st);
    dist[1] = 0x3f3f3f3f;
    q.push({0, 1});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (int v = 1; v <= n; ++v)
            if (g[u][v] && dist[v] < min(dist[u], g[u][v]))
                q.push({dist[v] = min(dist[u], g[u][v]), v});
    }
}
int main()
{
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i)
    {
        scanf("%d%d", &n, &m);
        memset(g, 0, sizeof g);
        for (int j = 1, a, b, c; j <= m; ++j)
        {
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = c;
        }
        dijkstra();
        printf("Scenario #%d:\n%d\n\n", i, dist[n]);
    }
    return 0;
}
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1001;
int T, t, n, m, p[N];
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w > a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
void kruskal()
{
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int j = 0; j < m; ++j)
    {
        int a = find(e[j].u), b = find(e[j].v);
        if (a != b)
            p[a] = b;
        if (find(1) == find(n))
        {
            printf("Scenario #%d:\n%d\n\n", t, e[j].w);
            break;
        }
    }
}
int main()
{
    scanf("%d", &T);
    for (t = 1; t <= T; ++t)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; ++i)
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        kruskal();
    }
    return 0;
}
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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1001;
int t, n, m, g[N][N], dist[N];
bool st[N];
int prim()
{
    memset(st, 0, sizeof st);
    memset(dist, 0, sizeof dist);
    dist[1] = 0x3f3f3f3f;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && (t == -1 || dist[t] < dist[j]))
                t = j;
        st[t] = 1;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && dist[j] < min(dist[t], g[t][j]))
                dist[j] = min(dist[t], g[t][j]);
    }
    return dist[n];
}
int main()
{
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i)
    {
        memset(g, 0, sizeof g);
        scanf("%d%d", &n, &m);
        for (int j = 1, a, b, c; j <= m; ++j)
        {
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = c, g[b][a] = c;
        }
        printf("Scenario #%d:\n%d\n\n", i, prim());
    }
    return 0;
}

POJ-3268 Silver Cow Party

有向图，多源，单终点，求往返路程最短路的最大值。可以将终点当作源点，正反建图，跑两次最短路算法，求和，最大值为答案。

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
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int N = 1001, M = 100001;
int n, m, x, a[M], b[M], t[M];
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], ans;
bool st[N];
void add(int u, int v, int ww)
{
    e[++idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx;
}
void dijstra(int dist[N])
{
    memset(st, 0, sizeof st);
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push({0, x});
    dist[x] = 0;
    while (q.size())
    {
        int u = q.top().second;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (int i = h[u]; i; i = ne[i])
        {
            int v = e[i];
            if (dist[v] > dist[u] + w[i])
                q.push({dist[v] = dist[u] + w[i], v});
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < m; ++i)
        scanf("%d%d%d", &a[i], &b[i], &t[i]);

    memset(h, 0, sizeof h);
    for (int i = 0; i < m; ++i)
        add(a[i], b[i], t[i]);
    memset(d1, 0x3f, sizeof d1);
    dijstra(d1);

    memset(h, 0, sizeof h);
    for (int i = 0; i < m; ++i)
        add(b[i], a[i], t[i]);
    memset(d2, 0x3f, sizeof d2);
    dijstra(d2);

    for (int i = 1; i <= n; ++i)
        if (i != x && ans < d1[i] + d2[i])
            ans = d1[i] + d2[i];
    printf("%d\n", ans);
    return 0;
}

POJ-1860 Currency Exchange

求正环，将传统 Bellman–Ford 算法改个方向即可。

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 101, M = 200;
int n, m, s, tol;
double v;
int e[M][2];
double w[M][2], dist[N];
bool bellmanford()
{
    memset(dist, 0, sizeof dist);
    dist[s] = v;
    for (int i = 1; i <= n; ++i)
    {
        bool flag = 0;
        for (int j = 0; j < tol; ++j)
        {
            int a = e[j][0], b = e[j][1];
            if (dist[b] < (dist[a] - w[j][1]) * w[j][0])
            {
                dist[b] = (dist[a] - w[j][1]) * w[j][0];
                flag = 1;
            }
        }
        if (!flag)
            return 0;
    }
    return 1;
}
int main()
{
    scanf("%d%d%d%lf", &n, &m, &s, &v);
    for (int i = 0, a, b; i < m; ++i)
    {
        double r1, c1, r2, c2;
        scanf("%d%d%lf%lf%lf%lf", &a, &b, &r1, &c1, &r2, &c2);
        e[tol][0] = a, e[tol][1] = b;
        w[tol][0] = r1, w[tol][1] = c1;
        ++tol;
        e[tol][0] = b, e[tol][1] = a;
        w[tol][0] = r2, w[tol][1] = c2;
        ++tol;
    }
    printf(bellmanford() ? "YES\n" : "NO\n");
    return 0;
}

POJ-3259 Wormholes

求负环。

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 501, M = 5200;
int t, n, m1, m2;
int e[M][2], w[M], dist[N], idx;
bool bellmanford()
{
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; ++i)
    {
        int flag = 1;
        for (int j = 0; j < idx; ++j)
        {
            int u = e[j][0], v = e[j][1];
            if (dist[v] > dist[u] + w[j])
            {
                dist[v] = dist[u] + w[j];
                flag = 0;
            }
        }
        if (flag) return 0;
    }
    return 1;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d", &n, &m1, &m2);
        idx = 0;
        for (int i = 0, a, b, c; i < m1; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            e[idx][0] = a, e[idx][1] = b, w[idx] = c;
            idx++;
            e[idx][0] = b, e[idx][1] = a, w[idx] = c;
            idx++;
        }
        for (int i = 0, a, b, c; i < m2; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            e[idx][0] = a, e[idx][1] = b, w[idx] = -c;
            idx++;
        }
        printf(bellmanford() ? "YES\n" : "NO\n");
    }
    return 0;
}

POJ-1502 MPI Maelstrom

单源多目的地最短路，取其中最大值，注意按示例输入建图。

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
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 101;
int n, g[N][N], dist[N];
bool st[N];
struct node
{
    int w, u;
    bool operator>(const node &a) const { return w > a.w; }
};
void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<node, vector<node>, greater<node> > q;
    q.push({0, 1});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (int v = 1; v <= n; ++v)
            if (dist[v] > dist[u] + g[u][v])
                q.push({dist[v] = dist[u] + g[u][v], v});
    }
}
int main()
{
    cin >> n;
    memset(g, 0x3d, sizeof g);
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j)
        {
            string s;
            cin >> s;
            if (s[0] == 'x')
                continue;
            int v = 0;
            for (int i = 0; i < s.size(); ++i)
                v *= 10, v += s[i] - '0';
            g[i][j] = g[j][i] = v;
        }
    dijkstra();
    cout << *max_element(dist + 2, dist + n + 1) << endl;
    return 0;
}

POJ-3660 Cow Contest

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
#include <iostream>
using namespace std;
const int N = 100;
int n, m, a, b, ans;
bool g[N][N];
int main()
{
    cin >> n >> m;
    while (m--)
    {
        cin >> a >> b;
        g[a - 1][b - 1] = 1;
    }
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                g[i][j] |= g[i][k] && g[k][j];
    for (int i = 0; i < n; ++i)
    {
        bool flag = 1;
        for (int j = 0; j < n; ++j)
            if (i != j && !g[i][j] && !g[j][i])
            {
                flag = 0;
                break;
            }
        if (flag)
            ++ans;
    }
    cout << ans << endl;
    return 0;
}

POJ-2240 Arbitrage

类似上面的Currency Exchange。

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 <cstring>
#include <map>
using namespace std;
const int N = 30, M = N * N;
int t, n, m;
int e[M][2];
double w[M], dist[N];
bool bellmanford()
{
    memset(dist, 0, sizeof dist);
    dist[0] = 1;
    for (int i = 0; i <= n; ++i)
    {
        bool flag = 0;
        for (int j = 0; j < m + n; ++j)
        {
            int a = e[j][0], b = e[j][1];
            if (dist[b] < dist[a] * w[j])
            {
                dist[b] = dist[a] * w[j];
                flag = 1;
            }
        }
        if (!flag)
            return 0;
    }
    return 1;
}
int main()
{
    while (cin >> n, n)
    {
        map<string, int> ccy;
        string c1, c2;
        for (int i = 0; i < n; ++i)
        {
            cin >> c1;
            ccy[c1] = i;
        }
        cin >> m;
        double r;
        for (int i = 0; i < m; ++i)
        {
            cin >> c1 >> r >> c2;
            e[i][0] = ccy[c1], e[i][1] = ccy[c2], w[i] = r;
        }
        for (int i = m; i < m + n; ++i)
            e[i][0] = m, e[i][1] = i - m, w[i] = 1;
        bool f = bellmanford();
        cout << "Case " << (++t) << ": "
             << (f ? "Yes" : "No") << endl;
    }
    return 0;
}

POJ-1511 Invitation Cards

单源多目的地最短路，一去一回，求和，回的时候反着建图就行。

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 <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e6 + 1, M = 2e6;
int t, n, m;
int h1[N], h2[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N];
bool st[N];
void add(int h[], int u, int v, int ww)
{
    e[idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx++;
}
struct node
{
    int w, u;
    bool operator>(const node &a) const { return w > a.w; }
};
void dijkstra(int h[], int d[])
{
    priority_queue<node, vector<node>, greater<node> > q;
    q.push({0, 1});
    d[1] = 0;
    memset(st, 0, sizeof st);
    while (q.size())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if (d[v] > d[u] + w[i])
                q.push({d[v] = d[u] + w[i], v});
        }
    }
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        memset(d1, 0x3f, sizeof d1);
        memset(d2, 0x3f, sizeof d2);
        idx = 0;
        for (int i = 0, a, b, c; i < m; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            add(h1, a, b, c);
            add(h2, b, a, c);
        }
        dijkstra(h1, d1);
        dijkstra(h2, d2);
        long long ans = 0;
        for (int i = 1; i <= n; ++i)
            ans += d1[i] + d2[i];
        printf("%lld\n", ans);
    }
    return 0;
}

POJ-3159 Candies

差分约束，注意比较方向。

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 <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 30001, M = 150001;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];
void add(int u, int v, int ww)
{
    e[++idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx;
}
struct node
{
    int w, u;
    bool operator>(const node &a) const { return w > a.w; }
};
void dijkstra()
{
    priority_queue<node, vector<node>, greater<node> > q;
    q.push({0, 1});
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    while (q.size())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (int i = h[u]; i; i = ne[i])
        {
            int v = e[i];
            if (d[v] > d[u] + w[i])
                q.push({d[v] = d[u] + w[i], v});
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0, a, b, c; i < m; ++i)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    dijkstra();
    printf("%d\n", d[n]);
    return 0;
}

POJ-2502 Subway

求最短路。注意处理好输入，建图 cost 要用时间而非距离以消弭速度差异，此外不能漏掉所有点之间的步行 cost，最后上最短路算法即可。

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int N = 310, INF = 1e9;
struct vertice
{
    double x, y;
} vs[N];
int n = 2;
double cost[N][N], d[N];
bool st[N];
struct node
{
    double w;
    int u;
    bool operator>(const node &a) const { return w > a.w; }
};
void dijkstra()
{
    for (int i = 2; i <= n; ++i)
        d[i] = INF;
    d[1] = 0;
    priority_queue<node, vector<node>, greater<node> > q;
    q.push({0, 1});
    while (q.size())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (int v = 1; v <= n; ++v)
            if (d[v] > d[u] + cost[u][v])
                q.push({d[v] = d[u] + cost[u][v], v});
    }
}
double get_dist(vertice &a, vertice &b)
{
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
int main()
{
    double v1 = 10000.0 / 60, v2 = 40000.0 / 60;
    scanf("%lf%lf%lf%lf", &vs[1].x, &vs[1].y, &vs[2].x, &vs[2].y);
    for (int i = 1; i <= 300; ++i)
        for (int j = 1; j <= 300; ++j)
            cost[i][j] = i == j ? 0 : INF;
    double x, y;
    while (~scanf("%lf%lf", &x, &y))
    {
        vs[++n] = {x, y};
        while (scanf("%lf%lf", &x, &y), x != -1)
        {
            vs[++n] = {x, y};
            cost[n][n - 1] = cost[n - 1][n] = min(cost[n][n - 1], get_dist(vs[n], vs[n - 1]) / v2);
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cost[i][j] = min(cost[i][j], get_dist(vs[i], vs[j]) / v1);
    dijkstra();
    printf("%d\n", (int)(d[2] + 0.5));
    return 0;
}

POJ-1062 昂贵的聘礼

等级差的限制是比较难处理的点。可以枚举等级差，再跑最短路。

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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 101, INF = 0x3f3f3f3f;
int m, n, p, level[N], x, t, v, w[N][N];
int q[N], hh, tt, dist[N], ans = INF;
bool st[N];
int dijkstra(int down, int up)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    hh = q[0] = dist[0] = 0, tt = 1;
    while (hh != tt)
    {
        int u = q[hh++];
        if (hh == N)
            hh = 0;
        st[u] = 0;
        for (int i = 1; i <= n; ++i)
            if (down <= level[i] && level[i] <= up && w[u][i] != INF && dist[i] > dist[u] + w[u][i])
            {
                dist[i] = dist[u] + w[u][i];
                if (!st[i])
                {
                    q[tt++] = i;
                    if (tt == N)
                        tt = 0;
                    st[i] = 1;
                }
            }
    }
    return dist[1];
}
int main()
{
    scanf("%d%d", &m, &n);
    memset(w, 0x3f, sizeof(w));
    for (int i = 1; i <= n; ++i)
        w[i][i] = 0;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d%d", &p, &level[i], &x);
        w[0][i] = p;
        while (x--)
        {
            scanf("%d%d", &t, &v);
            w[t][i] = min(w[t][i], v);
        }
    }
    for (int i = level[1] - m; i <= level[1]; ++i)
        ans = min(ans, dijkstra(i, i + m));
    printf("%d\n", ans);
    return 0;
}

POJ-1847 Tram

最短路，数量级小可以直接 Floyd。另外因为路径权值非 0 即 1，可以用 01-BFS。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 101, INF = 0x3f3f3f3f;
int n, a, b, 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()
{
    scanf("%d%d%d", &n, &a, &b);
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < n; ++i)
        g[i][i] = 0;
    for (int i = 1, k, v; i <= n; ++i)
    {
        scanf("%d", &k);
        int c = 0;
        while (k--)
            scanf("%d", &v), g[i][v] = c, c = 1;
    }
    floyd();
    printf("%d\n", g[a][b] == INF ? -1 : g[a][b]);
    return 0;
}
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 <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 101, INF = 0x3f3f3f3f;
int n, a, b, g[N][N], d[N];
bool st[N];
void bfs()
{
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);
    d[a] = 0;
    deque<int> q;
    q.push_back(a);
    while (q.size())
    {
        int u = q.front();
        q.pop_front();
        if (st[u])
            continue;
        st[u] = 1;
        for (int v = 1; v <= n; ++v)
        {
            if (d[v] > d[u] + g[u][v])
            {
                d[v] = d[u] + g[u][v];
                if (g[u][v] == 1)
                    q.push_back(v);
                else
                    q.push_front(v);
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &a, &b);
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < n; ++i)
        g[i][i] = 0;
    for (int i = 1, k, v; i <= n; ++i)
    {
        scanf("%d", &k);
        int w = 0;
        while (k--)
            scanf("%d", &v), g[i][v] = w, w = 1;
    }
    bfs();
    printf("%d\n", d[b] == INF ? -1 : d[b]);
    return 0;
}

LightOJ-1074 Extended Traffic

判负环，求最短路。

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
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 201, M = N * N;
int t, n, b[N], m, q;
int e[M][2], w[M], d[N];
bool st[N], flag[N];
void bellmanford()
{
    memset(d, 0, sizeof d);
    memset(flag, 0, sizeof flag);
    memset(st, 0, sizeof st);
    st[1] = 1;
    for (int k = 1; k < n; ++k)
    {
        for (int i = 0; i < m; ++i)
        {
            int u = e[i][0], v = e[i][1];
            if (st[u] && (!st[v] || d[v] > d[u] + w[i]))
                st[v] = 1, d[v] = d[u] + w[i];
        }
    }
    for (int i = 0; i < m; ++i)
    {
        int u = e[i][0], v = e[i][1];
        if (st[u] && (!st[v] || d[v] > d[u] + w[i]))
            flag[v] = 1;
    }
}
int main()
{
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> b[i];
        cin >> m;
        for (int i = 0, u, v; i < m; ++i)
        {
            cin >> u >> v;
            e[i][0] = u, e[i][1] = v, w[i] = pow(b[v] - b[u], 3);
        }
        bellmanford();
        cin >> q;
        cout << "Case " << _ << ":" << endl;
        while (q--)
        {
            cin >> m;
            if (flag[m] || d[m] < 3)
                cout << "?";
            else
                cout << d[m];
            cout << endl;
        }
    }
    return 0;
}

HDU-4725 The Shortest Path in Nya Graph

这一题考验建图。层与层连接，层与层内的点连接。建模：

  1. 可以虚拟出层点 ，
  2. 每一层和它的上一层以及下一层连接，代价为 0，这样就等于层层相连，
  3. 对于层内的点，建立层点到层内点的单向连接，代价为 c。（如果是双向连接，将导致原本不连通的点，如层内的两点，连通。）
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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 200002, M = 4 * N, INF = 0x3f3f3f3f;
int t, n, m, c, l[N];
int h[N], e[M], w[M], ne[M], idx, d[N];
bool st[N];
void add(int u, int v, int ww)
{
    e[idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx++;
}
struct node
{
    int w, u;
    bool operator>(const node &a) const { return w > a.w; }
};
void dijkstra()
{
    memset(st, 0, sizeof st);
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<node, vector<node>, greater<node>> q;
    q.push({0, 1});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        if (u == n)
            return;
        for (int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if (d[v] > d[u] + w[i])
                q.push({d[v] = d[u] + w[i], v});
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        cin >> n >> m >> c;
        memset(st, 0, sizeof st);
        for (int i = 1; i <= n; ++i)
        {
            cin >> l[i];
            add(l[i] + n, i, 0);
            st[l[i]] = 1;
        }
        for (int i = 1; i <= n; ++i)
        {
            if (l[i] >= 2 && st[l[i] - 1])
                add(i, l[i] - 1 + n, c);
            if (l[i] < n && st[l[i] + 1])
                add(i, l[i] + 1 + n, c);
        }
        for (int i = 1, a, b, c; i <= m; ++i)
        {
            cin >> a >> b >> c;
            add(a, b, c), add(b, a, c);
        }
        dijkstra();
        cout << "Case #" << _ << ": " << (d[n] != INF ? d[n] : -1) << endl;
    }
    return 0;
}

HDU-3416 Marriage Match IV

1
// TODO

HDU-4370 0 or 1

1
// TODO

POJ-3169 Layout

差分约束，判环，求最短路。

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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1001, M = 22000;
int n, ml, md;
int e[M][2], w[M], idx, d[N];
void add(int u, int v, int ww)
{
    e[idx][0] = u, e[idx][1] = v, w[idx] = ww, idx++;
}
bool bellmanford()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 1; i <= n; ++i)
    {
        int flag = 1;
        for (int j = 0; j < idx; ++j)
        {
            int u = e[j][0], v = e[j][1];
            if (d[v] > d[u] + w[j])
            {
                d[v] = d[u] + w[j];
                flag = 0;
            }
        }
        if (flag)
            return 0;
    }
    return 1;
}
int main()
{
    scanf("%d%d%d", &n, &ml, &md);
    for (int i = 0, a, b, d; i < ml; ++i)
    {
        scanf("%d%d%d", &a, &b, &d);
        if (a > b)
            swap(a, b);
        add(a, b, d);
    }
    for (int i = 0, a, b, d; i < md; ++i)
    {
        scanf("%d%d%d", &a, &b, &d);
        if (a > b)
            swap(a, b);
        add(b, a, -d);
    }
    for (int i = 1; i < n; ++i)
        add(i + 1, i, 0), add(0, i, 0);
    add(0, n, 0);
    printf("%d\n", bellmanford() ? -1 : (d[n] == 0x3f3f3f3f ? -2 : d[n]));
    return 0;
}