QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#758228 | #9431. The Quest for El Dorado | xiaofanger | WA | 0ms | 3544kb | C++17 | 1.4kb | 2024-11-17 16:54:01 | 2024-11-17 16:54:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int N = 5e5 + 10;
void solve() {
int n , m , k; cin >> n >> m >> k;
vector<priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>>> q(m + 1);
vector<vector<array<int , 3>>> e(n + 1);
for(int i = 1 ; i <= m ; i++){
int u , v , c , l; cin >> u >> v >> c >> l;
e[u].push_back({v , c , l});
e[v].push_back({u , c , l});
}
for(auto [v , c , l] : e[1]){
q[c].push({l , v});
}
vector<int> vis(n + 1 , 0);
vis[1] = 1;
for(int i = 1 ; i <= k ; i++){
int a , b; cin >> a >> b;
priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> cur;
while(q[a].size() && q[a].top().first <= b){
auto [w , v] = q[a].top();
cur.push({w , v});
q[a].pop();
}
while(cur.size()){
auto [w , u] = cur.top(); cur.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto [v , c , l] : e[u]){
if(vis[c]) continue;
if(c == a && w + l <= b){
cur.push({w + l , v});
}
else {
q[c].push({l , v});
}
}
}
}
for(int i = 1 ; i <= n ; i++) cout << vis[i];
cout << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int __ = 1;
cin >> __;
while(__--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3544kb
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:
11010 100
result:
wrong answer 1st lines differ - expected: '11011', found: '11010'