QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#749960 | #9431. The Quest for El Dorado | Yuu | WA | 125ms | 7156kb | C++23 | 2.8kb | 2024-11-15 11:40:44 | 2024-11-15 11:40:45 |
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::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});
}
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::set<int>del;
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);
}else{
break;
}
}else{
del.insert(v);
}
}
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 : del){
SG[c].erase(v);
}
for(auto v : newNode){
vis[v] = 1;
SG[c].erase(v);
}
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: 3592kb
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: -100
Wrong Answer
time: 125ms
memory: 7156kb
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:
1000000001000100000010000001000000000100000000 1000000010001001011011000000001000000100000000 1000000000000000000000000000000000000000000000 1011010000000010000100010011000100000000000010 1000000000000000000000101000010000001001000001 1000100010000000100000100000000000001010010 101010000000000000010...
result:
wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1000000001000100000010000001000000000100000000'