Kvar_ispw17's blog
0%

Posted on In

题目链接： HDU 3449 Flight

题目大意

给一个有向图带边权，求从给定的起点到终点的最短路，其中可以任选一条边把权值除二下取整，并仅能减一次。

题解

注意到，该问题仅与普通的最短路问题差一条边，我们首先把减半的边加到原图上，此时发现，不能满足仅使用一次，我们希望路径走了某一条减半边后不允许再走其他的减半边，剩下的到终点的路径则为普通路径，于是可以把原图复制一份，放在“另一层”，把所有的减半边连到层之间即可。

代码

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 * 2 + 5;
const int M = 5e5 * 5 + 5;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
    for(c = getchar(); !isdigit(c); c = getchar());
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

int hd[N], nxt[M], to[M], c[M], tot;
map<string, int> id;
int itot;
int n, m;

void add(int u, int v, int __c) {
    nxt[++tot] = hd[u], to[hd[u] = tot] = v, c[tot] = __c;
}

ll dis[N];

ll dijkstra(int S, int E) {
    // cout << S << " " << E << endl;
    dis[S] = 0;
    using Pair = pair<ll, int>;
    priority_queue<Pair, vector<Pair>, greater<Pair> > q;
    q.push(Pair(0, S));
    while(!q.empty()) {
        int u = q.top().second;
        q.pop();
        for(int e = hd[u]; e; e = nxt[e]) {
            int v = to[e];
            int w = c[e];
            if(dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                q.push(Pair(dis[v], v));
            }
        }
    }
    if(dis[E] == __LONG_LONG_MAX__) return -1;
    else return dis[E];
}

void init() { 
    for(int i = 0; i < N; i++) dis[i] = __LONG_LONG_MAX__;
#define mem(x) memset(x, 0, sizeof(x))
    mem(hd), mem(nxt), mem(to), mem(c);
    tot = itot = 0;
    id.clear();
}

int main() {
    // freopen("t3.in", "r", stdin);
    while(scanf("%d%d", &n, &m) != EOF) {
        // cout << n << " " << m << endl;
        init();
        for(int i = 1; i <= m; i++) {
            string a, b;
            int __c;
            cin >>  a >> b >> __c;
            int id1 = !id[a] ? id[a] = ++itot : id[a];
            int id2 = !id[b] ? id[b] = ++itot : id[b];
            add(id1, id2, __c);
            add(id1 + n, id2 + n, __c); // plus $n as the top layer
            add(id1, id2 + n, __c / 2); // floor the __c / 2
        }
        string s, e;
        cin >> s >> e;
        int __S = id[s];
        int __E = id[e] + n;
        if(__S == 0 || __E - n == 0) puts("-1");
        else cout << dijkstra(__S, __E) << endl;
    }
    return 0;
}