【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 - len
std::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();
}
}

原文地址：https://blog.csdn.net/Antonio915/article/details/142892548

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！