QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#749930 | #9431. The Quest for El Dorado | Yuu | TL | 874ms | 153984kb | C++23 | 3.0kb | 2024-11-15 11:32:02 | 2024-11-15 11:32:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
// The 2024 ICPC Kunming Invitational Contest
/*
Hint:
1.维护一个集合S,S由已遍历过的点组成。
维护S和非S点的边集{c, u, cost},假如存在多个cost,取最小的cost.
2.限制性最短路.
*/
void sol(){
int n, m, k;
std::cin>>n>>m>>k;
std::vector<std::map<int, std::vector<std::array<int, 2>>>>G(n + 1);
for(int i = 1;i <= m;i++){
int u, v, c, cost;
std::cin>>u>>v>>c>>cost;
G[u][c].push_back({v, cost});
G[v][c].push_back({u, cost});
}
// SG[c]:记录S的边集,c代表路的类型SG[c][v]:通过c路到达v的最低成本.
std::vector<std::map<int, int>>SG(m + 1);
std::vector<int>vis(n + 1);
vis[1] = 1;
{
for(auto [c, V] : G[1]){
for(auto [v, cost] : V){
if(SG[c].count(v) == 0){
SG[c][v] = cost;
}else{
SG[c][v] = std::min(SG[c][v], cost);
}
}
}
}
const int inf = 1E18;
std::vector<int>dis(n + 1, inf);
auto calc = [&](int c, int U){
std::set<int>newNode;
std::priority_queue<std::array<int, 2>, std::vector<std::array<int, 2>>, std::greater<>>Q;
for(auto [v, cost] : SG[c]){
if(vis[v] == 0){
if(cost <= U){
Q.push({dis[v] = cost, v});
newNode.insert(v);
}
}
}
// 不再使用S边集
while(Q.size()){
auto [cost, u] = Q.top();
Q.pop();
if(dis[u] < cost || G[u].count(c) == 0){
continue ;
}
auto& E = G[u][c];
for(auto [v, d] : E){
if(vis[v] == 0){
if(cost + d < dis[v] && cost + d <= U){
Q.push({dis[v] = cost + d, v});
newNode.insert(v);
}
}
}
}
// 加入新的点
for(auto v : newNode){
vis[v] = 1;
SG[c].erase(v);
}
// 拓展SG的边集
for(auto u : newNode){
for(auto& [cc, E] : G[u]){
for(auto [v, cost] : E){
if(vis[v] == 0){
if(SG[cc].count(v) == 0){
SG[cc][v] = cost;
}else{
SG[cc][v] = std::min(SG[cc][v], cost);
}
}
}
}
}
};
for(int i = 1;i <= k;i++){
int c, U;
std::cin>>c>>U;
calc(c, U);
}
for(int i = 1;i <= n;i++){
std::cout<<vis[i];
}
std::cout<<"\n";
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1; std::cin>>t;
while(t--) sol();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
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
output:
11011 100
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 250ms
memory: 7212kb
input:
1110 46 80 30 44 23 5 46 10 28 1 64 32 34 3 40 9 36 1 26 15 14 5 95 38 19 2 34 2 17 4 183 10 38 2 81 5 15 2 83 31 38 3 100 40 30 1 53 41 10 1 193 29 20 5 18 14 41 3 78 8 16 5 74 46 13 3 78 44 28 3 45 1 40 3 133 5 32 1 108 22 26 2 83 10 38 1 77 11 40 1 11 17 21 2 66 41 46 3 98 9 36 2 25 40 18 1 19 27...
output:
1000110011110111110010100001010100100101000000 1100010010111011011011000000011000001100001000 1000000000000000000000000000000000000000000000 1011010000000010000100010011000100000000000010 1000000000000000000000101000010000001001000001 1001100010110000100001100000000011001110110 101010000000000000010...
result:
ok 1110 lines
Test #3:
score: 0
Accepted
time: 181ms
memory: 8684kb
input:
1110 41 95 66 37 16 1 93 8 38 13 61 41 25 7 10 40 26 13 90 18 34 12 84 29 21 7 22 32 41 10 52 20 17 18 273 41 31 2 163 17 11 20 316 24 14 7 35 1 5 7 39 26 38 13 48 10 15 14 154 4 7 12 8 13 6 20 139 18 9 10 90 16 33 7 54 9 35 5 39 36 31 17 9 10 20 17 74 37 34 13 6 7 9 9 153 12 7 18 173 5 7 3 194 21 3...
output:
11111010101111111011111111101111111111011 11111111111111111111111111111111111111101 11111111111111111111111111111111111111111 11011110111111111111111111111011111111111 10100010011110000001010100010110010000001 111111111111111111111111111111111111111111 100000000000100000000000000100100000000000 1000...
result:
ok 1110 lines
Test #4:
score: 0
Accepted
time: 874ms
memory: 137564kb
input:
1 200000 500000 179 94800 107033 1 16 64316 117022 8 184 105481 172922 2 53 37627 148708 9 37 179021 41825 10 29 177650 69319 5 20 144968 160008 6 68 54796 172626 2 201 35718 99731 3 127 45553 132280 2 433 199580 18097 1 116 77143 7273 7 90 49300 94594 8 231 52637 197546 8 62 156375 4265 2 54 136509...
output:
111111111011001111111110110111111100000111111111111011101111011111110011111111011111111101100111111111110100111111101111111111111111111111111111111111111111111101111111111111111101111101010111111111111111110111111110111110111011010001110111111111111101111110011111111111111111110110111101011111111111...
result:
ok single line: '111111111011001111111110110111...1110101101101111110110011110111'
Test #5:
score: 0
Accepted
time: 724ms
memory: 153984kb
input:
1 200000 500000 28600 134923 17846 1145 19 38550 190638 1881 173 153445 161902 1019 61 134582 132451 1259 32 27836 81432 1053 99 45363 165206 1879 453 173218 82373 1834 392 36060 180829 1434 93 158792 24019 1305 80 114091 131741 400 36 86750 83631 674 284 102965 26889 903 96 72980 92116 852 293 7814...
output:
100101111101011111011110111110111110111001110111001100100011001111111011111101111011111010111010010010011101100111101010111010011101011111110111111101110110110111111111000110110101011110111011110111011011001111111101111110011111010111110100111111001111010110110111101111111011111101001011101110111010...
result:
ok single line: '100101111101011111011110111110...0111111111111110001011011001011'
Test #6:
score: 0
Accepted
time: 423ms
memory: 129084kb
input:
1 500000 500000 132 33565 62505 9 27 159690 223311 5 72 136509 402294 1 30 335433 250256 8 32 46344 199283 1 53 101509 318328 1 91 154342 472216 1 98 219655 19442 6 8 488718 58652 1 64 88757 14212 1 51 92129 332927 10 69 418031 387995 5 1 433240 214628 1 67 402161 87957 2 84 107282 385626 3 86 18834...
output:
100100000001001001011000000000010101010000100000000011010010000010000001000000100010000000101010100000011010001000011111000000101001000010010100101010110100010011000000000010000000111010101010011001011100000011000010100000001000010000001000010000001100010100000000001000010001000000001100110000010110...
result:
ok single line: '100100000001001001011000000000...0100010000000010000000000001101'
Test #7:
score: 0
Accepted
time: 515ms
memory: 131604kb
input:
1 500000 500000 34800 356922 276405 1274 6 70376 56771 944 85 311347 288381 114 23 323396 269923 1542 25 403829 492566 1731 41 415774 97020 149 48 317081 340484 627 3 277226 227941 1804 69 349022 434891 1274 53 436085 437523 1274 83 110761 403042 1180 86 333338 341167 1274 88 4802 451135 1149 18 116...
output:
111001100110001100011110001011001010001111100000011100001101000011100110010111011011101111101110010101011111110000111101100111101010111111100110001011111111101111100010101001110001110100100111010011110111001100011000111011111111111110010100111001111010011000111001111111111100111010001110011011111010...
result:
ok single line: '111001100110001100011110001011...1101000100101011111011001110110'
Test #8:
score: -100
Time Limit Exceeded
input:
1 200000 500000 500000 138435 172074 2 320 40030 9389 6 35 61974 124326 6 64 4679 144065 8 238 47254 185524 1 74 138009 134825 8 235 164764 59275 5 227 134478 183172 7 69 131920 51571 3 140 119971 193848 6 98 130747 49642 9 376 67838 127653 1 30 32972 140348 4 1 39560 183382 10 15 151497 1703 4 274 ...