QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750093 | #9431. The Quest for El Dorado | Yuu | TL | 212ms | 10872kb | C++23 | 3.3kb | 2024-11-15 12:36:03 | 2024-11-15 12:36:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
void sol(){
int n, m, k;
std::cin>>n>>m>>k;
std::vector<std::map<int, std::set<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].insert({cost, v});
G[v][c].insert({cost, u});
}
auto del = [&](int u, int v, int c, int cost){
G[u][c].erase({cost, v});
if(G[u][c].size() == 0){
G[u].erase(c);
}
};
std::vector<std::map<int, std::set<int>>>SG(m + 1);
{
// 初始化边集
std::vector<std::array<int, 4>>dell;
for(auto& [c, E] : G[1]){
for(auto& [cost, v] : E){
SG[c][cost].insert(v);
dell.push_back({1, v, c, cost});
}
}
for(auto [u, v, c, cost] : dell){
del(u, v, c, cost);
del(v, u, c, cost);
}
}
const int inf = 2E18;
std::vector<int>vis(n + 1);
std::vector<int>dis(n + 1, inf);
dis[1] = 0;
vis[1] = 1;
auto calc = [&](int c, int U){
if(SG[c].size() == 0) return ;
std::priority_queue<std::array<int, 2>, std::vector<std::array<int, 2>>, std::greater<>>Q;
std::set<int>nw;
std::vector<std::array<int, 2>>dl;
for(auto& [cost, V] : SG[c]){
if(cost > U) break;
for(auto v : V){
dl.push_back({cost, v});
if(vis[v] == 0){
if(dis[v] > cost){
Q.push({dis[v] = cost, v});
nw.insert(v);
}
}
}
}
for(auto [cost, u] : dl){
SG[c][cost].erase(u);
if(SG[c][cost].size() == 0){
SG[c].erase(cost);
}
}
while(Q.size()){
auto [d, u] = Q.top();
Q.pop();
if(dis[u] < d || G[u].count(c) == 0){
continue ;
}
auto& E = G[u][c];
for(auto [cost, v] : E){
if(cost + d > U) break;
if(vis[v] == 0 && dis[v] > cost + d){
Q.push({dis[v] = cost + d, v});
nw.insert(v);
}
}
}
// 加入新的点, 删除外点与内部点的边
std::vector<std::array<int, 4>>dell;
for(auto u : nw){
vis[u] = 1;
}
for(auto u : nw){
for(auto& [c, E] : G[u]){
for(auto& [cost, v] : E){
if(vis[v] == 0){
dell.push_back({u, v, c, cost});
SG[c][cost].insert(v);
}
}
}
}
for(auto [u, v, c, cost] : dell){
del(u, v, c, cost);
del(v, u, c, 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: 3540kb
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: 189ms
memory: 8944kb
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: 212ms
memory: 10872kb
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: -100
Time Limit Exceeded
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...