解題區/解題區 - UVa

UVa 13010 - Galactic taxes

contents

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

Problem

ACM 辦公室在銀河的各處，辦公室編號 $1$ 到 $N$，辦公室 $i$ 和辦公室 $j$ 之間的移動費用隨著時間 $t$ 成線性關係，假設移動不消耗時間，請決定移動時間 $t$，從辦公室 $1$ 移動到辦公室 $N$ 請問最少花費為何。

給定時間必須在一天以內完成，意即 $0 \le t \le 24 \times 60$。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2  1
1  2  1  0
5  8
1  2  27  610658
2  3  -48  529553
3  4  -6  174696
4  5  47  158238
3  5  84  460166
1  3  -21  74502
2  4  -13  858673
1  5  -90  473410
3  3
1  2  1  0
2  3  1  0
1  3  -1  1440
4  5
1  2  1  0
2  4  2  0
1  4  0  500
1  3  -1  1440
3  4  -2  2880
2  1
1  2  0  0

Sample Output

1
2
3
4
5
1440.00000
419431.27273
960.00000
500.00000
0.00000

Solution

明顯地，每一條邊花費都呈現線性關係，假設一張圖只有一條邊，依序加入新的邊進去，時間 $t$ 對應的路徑花費呈現凹性，因此三分搜尋時間 $t$，做一次 Dijkstra $\mathcal{O}(V \log E)$。由於需要精準度到小數五位，估計要到至少三分 50 次，總時間複雜度 $\mathcal{O}(100 V \log E)$。

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
const int MAXV = 2048;
const int MAXE = 131072;
const long long INF = 1e+60;
struct Edge {
    int to, eid;
    double w;
    Edge *next;
};
Edge edge[MAXE], *adj[MAXV];
int e = 0;
double dist[MAXV];
void addEdge(int x, int y, double v)  {
    edge[e].to = y, edge[e].w = v, edge[e].eid = e;
    edge[e].next = adj[x], adj[x] = &edge[e++];
}
void dijkstra(int st, double dist[], int n) {
    typedef pair<double, int> PLL;
    for (int i = 0; i <= n; i++)
        dist[i] = INF;
    set<PLL> pQ;
    PLL u;
    pQ.insert(PLL(0, st)), dist[st] = 0;
    while (!pQ.empty()) {
        u = *pQ.begin(), pQ.erase(pQ.begin());
        for (Edge *p = adj[u.second]; p; p = p->next) {
            if (dist[p->to] > dist[u.second] + p->w) {
                if (dist[p->to] != INF)
                    pQ.erase(pQ.find(PLL(dist[p->to], p->to)));
                dist[p->to] = dist[u.second] + p->w;
                pQ.insert(PLL(dist[p->to], p->to));
            }
        }
    }
}
int I[MAXE], J[MAXE], A[MAXE], B[MAXE];
double f(int N, int M, double t) {
    e = 0;
    for (int i = 1; i <= N; i++)
        adj[i] = NULL;
    for (int i = 0; i < M; i++) {
        double cost = t * A[i] + B[i];
        addEdge(I[i], J[i], cost);
        addEdge(J[i], I[i], cost);
    }
    
    dijkstra(1, dist, N);
    return dist[N];
}
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < M; i++)
            scanf("%d %d %d %d", &I[i], &J[i], &A[i], &B[i]);
        double l = 0, r = 24 * 60, mid, midmid, md, mmd;
        double ret = 0;
        for (int it = 0; it < 100; it++) {
            mid = (l+r)/2;
            midmid = (mid+r)/2;
            md = f(N, M, mid);
            mmd = f(N, M, midmid);
            ret = max(ret, md);
            if (fabs(md - mmd) < 1e-6)
                break;
            if (md < mmd)
                l = mid;
            else
                r = midmid;
        }
        printf("%.5lf\n", ret);
    }
    return 0;
}