The way home

发表于 分类于 ，

    一个人在一张有向图的 $1$ 号结点，他要去到 $n$ 结点。每条边 $(a_i,b_i)$ 有边权 $s_i$，表示走过这条边需要花 $s_i$ 元。这个人一开始有 $p$ 元，到了一个点 $u$，他可以进行若干次演出，每次演出收获 $w_u$ 元。问到达 $n$ 的最小演出次数，若无解输出 -1。

The way home

Created by LXC on Thu Apr 4 18:54:24 2024

https://codeforces.com/problemset/problem/1801/D

ranting: 2100

tag: binary search, data structures, dp, graphs, greedy, shortest paths, sortings

problem

一个人在一张有向图的 $1$ 号结点，他要去到 $n$ 结点。每条边 $(a_i,b_i)$ 有边权 $s_i$，表示走过这条边需要花 $s_i$ 元。这个人一开始有 $p$ 元，到了一个点 $u$，他可以进行若干次演出，每次演出收获 $w_u$ 元。问到达 $n$ 的最小演出次数，若无解输出 -1。

solution

类似dijkstra

设$f_{i, j}=(step, coins)$为从1到达第i个点时，路径上最大演出费用节点为$j$，所得到的最少步数step和金币coins，并且在step相等时coins选择最大化。

设$f_{u,m}=(s,c)$已经求出，从u节点存在指向v节点的权值为d的有向边，
那么我们可松弛$f_{v,y}=(s+k,c+kw_m-d)$,其中$k = \lceil \frac{max(0,d-c)}{w_m} \rceil$,$y=w_v>w_m?v:m$

code

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", \n"; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

const ll INF = 0x3f3f3f3f3f3f3f3f;

struct Value {
    ll s, m;
    Value(ll s=INF, ll m=0):s(s), m(m) {}
    bool operator<(const Value& o) const {
        if (o.s == s) return m < o.m;
        return s > o.s;
    }
    bool operator!=(const Value& o) const {
        return m != o.m || s != o.s;
    }
};
ostream& operator<<(ostream& os, const Value& v) {
    os<<'['; 
    auto [s, m] = v;
    os << s << ", " << m;
    return os<<']';
}

struct Node {
    int p, mp;
    Value v;
    Node(int p, int mp, Value v): p(p), mp(mp), v(v) {}
    bool operator<(const Node& o) const {
        return v < o.v;
    }
};

void sol() {
    ll n, m, p;
    cin >> n >> m >> p;
    vector<ll> w(n+1);
    for (int i=1; i<=n; i++) {
        cin >> w[i];
    }
    vector<vector<pair<ll,ll>>> g(n+1);
    for (int i=0; i<m; i++) {
        ll a, b, s;
        cin >> a >> b >> s;
        g[a].emplace_back(b, s);
    }
    vector<vector<Value>> f(n+1, vector<Value>(n+1));
    f[1][1] = {0, p};
    priority_queue<Node> pq;
    pq.emplace(1, 1, f[1][1]);
    while (pq.size()) {
        auto c = pq.top(); pq.pop();
        auto [a, b, s] = c;
        // if (s != f[a][b]) continue;
        for (auto& [u, v]:g[a]) {
            int y = w[b] > w[u] ? b:u;
            auto [s1, m1] = s;
            ll k = (max(v-m1, 0LL)+w[b]-1)/w[b];
            Value t(s1+k, m1+k*w[b]-v);
            // cout << u << " " << v << " " << t << endl;
            if (f[u][y] < t) {
                f[u][y] = t;
                pq.emplace(u, y, t);
            }
        }
    }
    // cout << f << endl;
    ll ans = INF;
    for (int i=1; i<=n; i++) {
        ans = min(ans, f[n][i].s);
    }
    if (ans == INF) cout << "-1\n";
    else cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}