QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#710776 | #9431. The Quest for El Dorado | libantian | WA | 81ms | 5168kb | C++23 | 1.8kb | 2024-11-04 21:41:59 | 2024-11-04 21:42:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, m, k;
cin >> n >> m >> k;
using E = array<int, 3>;
using P = pair<int64_t, int64_t>;
vector<E> g[n + 1];
for (int i = 0; i < m; i++)
{
int u, v, c, l;
cin >> u >> v >> c >> l;
g[u].push_back({v, c, l});
g[v].push_back({u, c, l});
}
vector<int> vis(n + 1);
vector<priority_queue<P>> q(m + 1);
vis[1] = 1;
for (auto [v, c, l] : g[1])
q[c].push(P(-l, v));
for (int it = 0; it < k; it++)
{
int C, L;
cin >> C >> L;
vector<P> tmp;
while (!q[C].empty())
{
auto [l, u] = q[C].top();
l = -l;
if (l > L)
break;
q[C].pop();
if (vis[u])
continue;
vis[u] = 1;
for (auto [v, c, w] : g[u])
{
if (vis[v])
continue;
if (c == C)
{
//tmp.push_back(P(-w, v));
q[c].push(P(-(l + w), v));
}
else
{
q[c].push(P(-w, v));
}
}
}
// for(auto [l,u] : tmp)
// {
// if (vis[u])
// continue;
// q[C].push(P(l,u));
// }
}
for(int i = 1;i <= n;i++)
cout << vis[i];
cout << '\n';
}
int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
auto _ = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
#ifdef LOCAL
cerr << clock() - _ << '\n';
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
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: 81ms
memory: 5168kb
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 1000000010101001011011000000001000000100001000 1000000000000000000000000000000000000000000000 1011000000000000000100000010000000000000000010 1000000000000000000000001000010000001001000001 1001100010100000100001100000000011001110110 100010000000000000010...
result:
wrong answer 2nd lines differ - expected: '1100010010111011011011000000011000001100001000', found: '1000000010101001011011000000001000000100001000'