Codeforces Round 857 (Div. 1) D/(Div. 2) F

题目链接：The way home

题解：Dijkstra

1. 题目中包含的重要信息

1. 每个城市可以举办的表演次数是不限的，这意味着只要起始点到终点存在一条路径就一定能有解

1. n和m的范围都很小，支持O(n^2)的算法复杂度

(下文字符释义：u——当前城市、v——下一个城市、w(u, v)——u到v的路费、src——起始点、dst——终点、a->b——a到b）

1. 思考过程

1. 图论问题找两点的最小解很容易想到Dijkstra算法

1. 考虑每个结点需要维护的信息：

1. src->u所需要举办的最小表演次数cnt[u]

1. 光有cnt[i]是没办法状态转移的，比较自然地能想到我们还需要记录cnt[u]对应的余额res[u]

1. 有了上面两个信息我们考虑状态的转移过程：

1. 如果res[u]>w(u, v)则不需要进行表演，余额减少

1. 如果res[u]<w(u, v)，我们需要在src->u中获利最大的城市(假设该城市每次获利mx)进行表演，表演次数为能支付路费的最小表演次数。mx怎么记录呢，细想一下我们可以发现，src->u的路径可能很多，不同路径的mx可能不同，我们不能只记录cnt和res最优时对应mx，因为可能存在cnt和res不是最优但是mx很大的路径，这种情况可能会影响到后续点的最优解

1. 所以一个结点的状态应该包含src->u的路径中所有可能mx以及每个mx对应的最优cnt和res

1. 算法过程：

1. 状态定义：

1. cnt[i][j]：src->i，路径中mx为j时最少演出次数

1. res[i][j]：最多余额；因为mx的数据范围很大，所以这里是离散化后的值

1. 状态转移：

1. Dijkstra的处理方法，优先找“最近的”点进行更新

1. “最近的”：

1. 如果mx不同则优先访问mx最小的点

1. 否则，优先访问cnt最小的点

1. 否则，优先访问res最大的点

1. ans = min(cnt[n][j])

代码示例：

<code class="language-plaintext hljs">#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
#include <list>
#include <bitset>
#include <utility>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <string>
#include <sstream>
#include <functional>
#include <cstdlib>
#include <string.h>
#include <bitset>
#include <string_view>
#include <thread>
#include <future>
#include <random>

#define ll        long long
#define ull        unsigned long long
#define srt        short

template<class _Tp>
struct GT {
    constexpr bool operator()(const _Tp& a, const _Tp& b) const { return a > b; }
};

template<class _Tp>
struct LS {
    constexpr bool operator()(const _Tp& a, const _Tp& b) const { return a < b; }
};


const int N = 801, M = 3001;
int t, n, m, p;
int h[N], ne[M], to[M], wt[M], idx;
void Add(int u, int v, int w) {
    to[idx] = v, wt[idx] = w, ne[idx] = h[u], h[u] = idx++;
}

int g[N], tot;
// g[i]的离散值
int gGuide[N];

// 从源点到达i点，路径中max(g)为g[gGuide[j]]时
// 最少演出次数
ll cnt[N][N];
// 最多余额
ll res[N][N];

class Pr {
public:
    // 当前位置
    int u;
    // 路径上max(g)的离散值
    int mx;
    Pr() = default;
    Pr(int _u, int _mx) :u(_u), mx(_mx) {}

    bool operator < (const Pr& cpr) const {
        if (this->mx != cpr.mx) return this->mx > cpr.mx;
        if (cnt[this->u][mx] != cnt[cpr.u][mx]) return cnt[this->u][mx] > cnt[cpr.u][mx];
        return res[this->u][mx] < res[cpr.u][mx];
    }
};

// 封闭列表
bool close[N][N];

void Dijkstra() {
    for (int i = 1; i <= n; i++) {
        std::fill_n(&cnt[i][1], tot, std::numeric_limits<ll>::max());
        std::fill_n(&close[i][1], tot, false);
    }

    std::priority_queue<Pr> qu;

    int j = gGuide[1];
    cnt[1][j] = 0;
    res[1][j] = p;
    qu.emplace(1, j);

    int u, v, w, mx;
    while (qu.size()) {
         u = qu.top().u;
         mx = qu.top().mx;
        qu.pop();

        if (close[u][mx]) continue;
        close[u][mx] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            v = to[i];
            w = wt[i];
            j = gGuide[v];
            int mmx = std::max(j, mx);
            if (close[v][mmx]) continue;
            ll cntu = cnt[u][mx];
            ll resu = res[u][mx];
            if (resu < w) {
                ll tmp = (w - resu) / g[mx] + ((w - resu) % g[mx] != 0);
                cntu += tmp;
                resu += tmp * g[mx];
            }
            resu -= w;
            if (cnt[v][mmx] > cntu || cnt[v][mmx] == cntu && res[v][mmx] < resu) {
                cnt[v][mmx] = cntu;
                res[v][mmx] = resu;
                qu.emplace(v, mmx);
            }
        }
    }
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &p);

        std::fill_n(h + 1, n, -1);
        idx = 0;

        for (int i = 1; i <= n; i++) {
            scanf("%d", g + i);
            gGuide[i] = g[i];
        }

        int u, v, s;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &s);
            Add(u, v, s);
        }

        // 离散化操作
        std::sort(g + 1, g + 1 + n);
        tot = std::unique(g + 1, g + 1 + n) - g - 1;
        for (int i = 1; i <= n; i++) gGuide[i] = std::lower_bound(g + 1, g + 1 + tot, gGuide[i]) - g;

        Dijkstra();
        ll ans = std::numeric_limits<ll>::max();
        for (int i = 1; i <= tot; i++) ans = std::min(ans, cnt[n][i]);
        if (ans == std::numeric_limits<ll>::max()) puts("-1");
        else printf("%lld\n", ans);
    }

    return 0;
}

</code>