【ICPC】The 2024 ICPC Kunming Invitational Contest J

The Quest for El Dorad

#最短路 #图论 #数据结构 #二分

题目描述

There is a kingdom with $n$ cities and $m$ bi-directional railways connecting the cities. The $i$-th railway is operated by the $c_i$-th railway company, and the length of the railway is $l_i$.

You’d like to travel around the country starting from city $1$. For your travel, you have bought $k$ railway tickets. The $i$-th ticket can be represented by two integers $a_i$ and $b_i$, meaning that if you use this ticket, you can travel through some railways in one go, as long as they’re all operated by company $a_i$ and their total length does not exceed $b_i$. It is also allowed to just stay in the current city when using a ticket. You can only use the tickets one at a time, and you can only use each ticket once.

As you find it a burden to determine the order to use the tickets, you decided to use the tickets just in their current order. More formally, you’re going to perform $k$ operations. In the $i$-th operation, you can either choose to stay in the current city $u$; Or choose a different city $v$, such that there exists a path from city $u$ to city $v$ where all railways in the path are operated by company $a_i$ and the total length of railways does not exceed $b_i$, and finally move to city $v$.

For each city, determine if it is possible to arrive in that city after using all $k$ tickets.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$, and $k$ ($2\le n\le 5\times 10^5$, $1\le m\le 5\times 10^5$, $1\le k\le 5\times 10^5$) indicating the number of cities, the number of railways and the number of tickets.

For the following $m$ lines, the $i$-th line contains four integers $u_i$, $v_i$, $c_i$, and $l_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$, $1\le c_i\le m$, $1\le l_i\le 10^9$) indicating that the $i$-th railway connects city $u_i$ and $v_i$. It is operated by company $c_i$ and its length is $l_i$. Note that there might be multiple railways connecting the same pair of cities.

For the following $k$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1\le a_i\le m$, $1\le b_i\le 10^9$) indicating that if you use the $i$-th ticket, you can travel through some railways in one go, if they’re all operated by company $a_i$ and their total length does not exceed $b_i$.

It’s guaranteed that the sum of $n$, the sum of $m$, and the sum of $k$ of all test cases will not exceed $5\times 10^5$.

输出格式

For each test case, output one line containing one string $s_1{s}_2\cdots s_n$ of length $n$ where each character is either $0$ or $1$. If you can travel from city $1$ to city $i$ with these $k$ tickets, then $s_i=1$; Otherwise $s_i=0$.

样例 #1

样例输入 #1

2
5 6 4
1 2 1 30
2 3 1 50
2 5 5 50
3 4 6 10
2 4 5 30
2 5 1 40
1 70
6 100
5 40
1 30
3 1 1
2 3 1 10
1 100

样例输出 #1

11011
100

解题思路

首先，操作顺序是固定的，对于一条线路（边），我们能做的只有选择这张车票坐下去（如果可以），或者等待到下一张可行的票。

因此，这可以看做是一个$dijkstra$的最短路，我们以操作次数作为第一关键字，以已经乘坐了的线路长度作为第二关键字，从小到大的取出来转移：

$1.$ 如果当前路径是同一个公司，并且加上这条边的权重不会超过这张票的最大权重，那么我们直接转移

$2.$ 反之，我们就可以找到第一个为这个公司，并且票的权重大于这条边的票作为转移。

那么，对于一个无序的序列，找到$[l,r]$第一个大于等于$x$的数，可以使用二分+$RMQ$算法来实现，这里使用$ST$表，预处理后可以配合二分实现$lo{g}_n$查询。

总体时间复杂度在$O(klo{g}_{2}k+nlo{g}_2(n+m)lo{g}_{2}k)$

代码

using pii = std::pair<int, int>;const int N = 5e5 + 10;int LOG[N];
struct STList {int n, k;std::vector<std::vector<int>> Max;STList() {}STList(const std::vector<int>& a) {init(a);}void init(const std::vector<int>& a) {n = a.size();k = LOG[n] + 1;Max.assign(n, std::vector<int>(k));for (int i = 0; i < n; ++i) {Max[i][0] = a[i];}for (int j = 1; j < k; ++j) {for (int i = 0; i + (1LL << j) <= n; ++i)Max[i][j] = std::max(Max[i][j - 1], Max[i + (1LL << (j - 1))][j - 1]);}}int query(int l, int r) {int j = LOG[r - l + 1];return std::max(Max[l][j], Max[r - (1LL << j) + 1][j]);}
};struct node {int v, c, dis;
};void solve() {int n, m, k;std::cin >> n >> m >> k;std::vector<std::vector<node>>e(n + 1);for (int i = 1; i <= m; ++i) {int u, v, c, dis;std::cin >> u >> v >> c>> dis;e[u].push_back({ v,c,dis });e[v].push_back({ u,c,dis });}std::vector<std::vector<int>>mx(m + 1);std::vector<pii>a(k + 1); //c - lenstd::vector<std::vector<int>>idx(m + 1);for (int i = 1; i <= k; ++i) {int c, l;std::cin >> c >> l;a[i] = { c,l };mx[c].push_back(l);idx[c].push_back(i);}std::vector<STList>ST(m + 1);for (int i = 1; i <= m; ++i) {if (mx[i].empty()) continue;ST[i].init(mx[i]);}std::vector<int> ok(n + 1), vis(n + 1);auto dijkstra = [&]() {//turn - dis - v std::priority_queue<std::array<int,3>, std::vector<std::array<int, 3>>,greater<>>pq; pq.push({ 1,0,1 });while (pq.size()) {auto [turn, dis, u] = pq.top(); pq.pop();if (vis[u]) continue;vis[u] = 1; ok[u] = 1;for (auto& [v, C, Dis] : e[u]) {if (mx[C].empty()) continue;auto& [c, D] = a[turn];if (C == c && Dis + dis <= D) {if (vis[v] == 0) {pq.push({ turn, Dis + dis, v });}continue;}auto pos = lower_bound(idx[C].begin(), idx[C].end(), turn + 1) ;if (pos == idx[C].end()) continue;int L = std::distance(idx[C].begin(), pos), R = idx[C].size() - 1;if (ST[C].query(L, R) < Dis) continue;int l = L, r = R, ans = -1;while (l <= r) {int mid = l + r >> 1;if (ST[C].query(l, mid) >= Dis) {r = mid - 1;ans = idx[C][mid];}else {l = mid + 1;}}pq.push({ ans,Dis,v });}}};dijkstra();for (int i = 1; i <= n; ++i) {std::cout << ok[i];}std::cout << "\n";}void init() {LOG[0] = -1;for (int i = 1; i < N; ++i) {LOG[i] = LOG[i >> 1] + 1;}}
signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;std::cin >> t;init();while (t--) {solve();}
}