题解：CF1915G Bicycles

· · 题解

思路：分层图最短路

明显，在有多辆车的情况下，使用速度系数最小的车最优。

但是，如果直接跑普通的最短路，样例会过不了。

为什么？

首先观察样例所建的图：

当从 1 到 2 时所花的时间是 10。如果直接跑最短路的话，路径是 1 \to 2 \to 4 \to 5。总时间是 2 \times 5 + 2 \times 5 + 2\times 1 = 22。

但是，实际上路径为 1 \to 2 \to 3 \to 2 \to 4 \to 5 是会更优的，总时间是 2 \times 5 + 1 \times 2 + 1 \times 1 + 5 \times 1 + 1\times 1 = 19。观察两个路径的区别，不难发现，在第二种中虽然重复走了两遍 2 \to 3 但这换取了速度系数更小，使得总时间更少。

所以我们对于每一个速度系数建一个层，跑一遍分层图最短路即可。注意能往下一层转移的，就不必再在同层转移了。

对比：

对于答案，即为 \min^{1000}_{i = 1} d_{n,i}。其中 d_{i,j} 表示从 1 到 i，且最小速度系数最小值为 j 时的最短时间。

code：

#include <bits/stdc++.h>
using namespace std;

#define inf 0x7fffffffffffffff
int n, m;

struct V{
    int s;
    vector<array<int, 2> > e;
    long long d[1009];
    bitset<1009> c;
}v[1009];

priority_queue<array<long long, 3>, vector<array<long long, 3> >, greater<array<long long, 3> > > p;

inline void dij() {
    p.push({0, 1, v[1].s});
    v[1].d[v[1].s] = 0;
    while(p.size()) {
        int u = p.top()[1];
        int k = p.top()[2];
        p.pop();
        if(v[u].c[k]) continue;
        v[u].c = 1;

        for(auto to: v[u].e) {
            if(v[to[0]].d[min(k, v[to[0]].s)] > v[u].d[k] + to[1] * k) {
                v[to[0]].d[min(k, v[to[0]].s)] = v[u].d[k] + to[1] * k;
                p.push({v[to[0]].d[min(k, v[to[0]].s)], to[0], min(k, v[to[0]].s)});
            }
        }
    }
}

inline void sovel() {
    cin >> n >> m;
    fill(v + 1, v + n + 1, v[0]);
    for(int i = 1, _u, _v, _w; i <= m; i++) {
        cin >> _u >> _v >> _w;
        v[_u].e.push_back({_v, _w});
        v[_v].e.push_back({_u, _w});
    }
    for(int i = 1; i <= n; i++) {
        fill(v[i].d + 1, v[i].d + 1001, inf);
        cin >> v[i].s;
    }
    dij();
    long long ans = inf;
    for(int i = 1; i <= 1000; i++) {
        ans = min(ans, v[n].d[i]);
    }
    cout << ans << "\n";
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int _T = 1;
    cin >> _T;
    while(_T--) {
        sovel();
    }

    return 0;

}