解題區/解題區 - UVa

UVa 11097 - Poor My Problem!

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一張圖 (有向圖)，請問從起始點走到特定點的路徑，花費 / 經過邊數 最小值為何？

並且最多經過 1000 條邊 (含)，邊可以重複走。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3 2 0
0 1 100
1 2 200
3
0
1
2
 
5 5 0
0 1 3
1 2 4
2 3 5
2 4 6
4 3 1
2
2
3

Sample Output

1
2
3
4
5
6
0.0000 0
100.0000 1
150.0000 2
3.5000 2
3.5000 4

Solution

如果沒有限制最多經過的邊，將會相當難辦事，因為一直繞就可以將平均值拉下，而會繞多久可能要玩一下環狀收斂，最小平均環，然後檢查是否會經過這個環抵達目的地 …

當然這一題已經給定最大使用邊數，定義狀態為 dp[i][j] 使用 j 條邊抵達目的地 i 的最小花費。按照 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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
    int to, w;
    edge(int a = 0, int b = 0):
        to(a), w(b) {}
};
vector<edge> g[1024];
int dp[1024][1024], inq[1024][1024];
const int MAXE = 1000;
void solve(int source, int N) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= MAXE; j++)
            dp[i][j] = 0x3f3f3f3f;
    queue<int> X, E;
    int u, v, w, e;
    dp[source][0] = 0;
    X.push(source), E.push(0);
    while (!X.empty()) {
        u = X.front(), X.pop();
        e = E.front(), E.pop();
        inq[u][e] = 0;
        if (e == MAXE)	continue;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].to, w = g[u][i].w;
            if (dp[v][e+1] > dp[u][e] + w) {
                dp[v][e+1] = dp[u][e] + w;
                if (!inq[v][e+1]) {
                    inq[v][e+1] = 1;
                    X.push(v), E.push(e+1);
                }
            }
        }
    }
}
int main() {
    int N, M, S, Q;
    int x, y, w;
    while (scanf("%d %d %d", &N, &M, &S) == 3) {
        for (int i = 0; i < N; i++)
            g[i].clear();
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(edge(y, w));
        }
        
        solve(S, N);
        
        scanf("%d", &Q);
        while (Q--) {
            scanf("%d", &x);
            double ret = 1e+30;
            int e = -1;
            if (x == S)
                ret = 0, e = 0;
            else {
                for (int i = 1; i <= MAXE; i++) {
                    if (dp[x][i] != 0x3f3f3f3f) {
                        if ((double)dp[x][i]/i < ret) {
                            ret = (double)dp[x][i]/i;
                            e = i;
                        }
                    }
                }
            }
            if (e == -1)
                puts("No Path");
            else
                printf("%.4lf %d\n", ret, e);
        }
        puts("");
    }
    return 0;
}