AtCoder Beginner Contest 192 E.Train

题目链接

Problem Statement

In the Republic of AtCoder, there are N cities numbered 1 through N and M
railroads numbered 1 through M.

Railroad i connects City $A_i$ and City $B_i$ bidirectionally. At time 0, $K_i$, and all subsequent multiples of $K_i$, a train departs from each of these cities and head to the other city. The time each of these trains takes to reach the destination is $T_i$.

You are now at City X. Find the earliest time you can reach City Y when you start the journey by taking a train that departs City X not earlier than time 0. If City Y is unreachable, report that fact.

The time it takes to transfer is ignorable. That is, at every city, you can transfer to a train that departs at the exact time your train arrives at that city.

Sample Input 1

3 2 1 3
1 2 2 3
2 3 3 4

Sample Output 1

7

Sample Input 2

3 2 3 1
1 2 2 3
2 3 3 4

Sample Output 2

5

Sample Input 3

3 0 3 1

Sample Output 3

-1

Sample Input 4

9 14 6 7
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
2 3 8 4
6 2 6 4
3 8 3 2
7 9 5 2
8 4 1 9
7 1 6 9
3 9 9 3
7 5 1 5
8 2 9 7
4 9 4 4

Sample Output 4

26

最短路~
我们可以把时间看成距离，对任意两点 $A_i$ 和 $B_i$，已知其中一点的时间 $t$，那么到达另一点的时间就是 $\lceil\frac{t}{K_i}\rceil*K_i+T_i$，知道这一点后就可以套最短路计算了，有两种方法：

• dijkstra算法+堆优化
• BFS+堆优化

两者复杂度差不多，我采取的是后者，AC代码如下：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N = 1e5 + 5;
vector<tuple<int, ll, ll>> G[N];
int n, m, u, v, x, y, vis[N];
ll t, k, d[N];

void bfs() {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
    fill(d, d + N, 1e18);
    d[x] = 0;
    q.push({0, x});
    while (!q.empty()) {
        auto[t, a] = q.top();
        q.pop();
        if (a == y) break;
        if (t > d[a]) continue;
        for (auto[b, t, k]:G[a]) {
            t = (d[a] + k - 1) / k * k + t;
            if (d[b] > t) {
                d[b] = t;
                q.emplace(d[b], b);
            }
        }
    }
}

int main() {
    cin >> n >> m >> x >> y;
    while (m--) {
        cin >> u >> v >> t >> k;
        G[u].emplace_back(v, t, k);
        G[v].emplace_back(u, t, k);
    }
    bfs();
    if (d[y] == 1e18) cout << -1;
    else cout << d[y];
    return 0;
}