QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#694740 | #6523. Escape Plan | Shuishui# | WA | 1057ms | 67208kb | C++14 | 1.5kb | 2024-10-31 18:33:39 | 2024-10-31 18:33:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define Sz(x) (int)(x).size()
#define bit(x) (1ll << (x))
using ll = long long;
using db = double;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vd = vector<db>;
mt19937 mrand(time(0));
void solve(void)
{
int n, m, k;
cin >> n >> m >> k;
const ll INF = bit(60);
vl dis(n + 2, INF);
priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> q;
for (int i = 1; i <= k; i++)
{
int x;
cin >> x;
dis[x] = 0;
q.push({dis[x], x});
}
vi d(n + 2);
for (int i = 1; i <= n; i++)
{
cin >> d[i];
if (!dis[i]) d[i] = 0;
}
vector<vector<array<int, 2>>> e(n + 2);
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
e[u].pb({v, w}), e[v].pb({u, w});
}
while (!q.empty())
{
auto [ndis, u] = q.top();
q.pop();
if (d[u])
{
d[u]--;
continue;
}
dis[u] = ndis;
for (auto [v, w] : e[u])
if (dis[u] + w < dis[v])
q.push({dis[u] + w, v});
}
if (dis[1] == INF)
cout << -1 << "\n";
else
cout << dis[1] << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// cout << fixed << setprecision(10);
int T = 1;
cin >> T;
for (int i = 1; i <= T; i++)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3696kb
input:
2 3 4 1 3 1 1 1 1 2 1 1 2 2 2 3 1 2 3 2 3 2 2 2 3 2 0 0 1 2 1 1 3 1
output:
4 -1
result:
ok 2 number(s): "4 -1"
Test #2:
score: -100
Wrong Answer
time: 1057ms
memory: 67208kb
input:
100 100 1808 2 94 47 3 3 0 2 4 3 3 4 0 0 2 2 2 3 2 4 0 2 3 4 4 2 0 3 4 3 1 0 2 1 2 2 0 3 4 4 4 1 2 2 3 1 0 0 3 1 4 2 1 3 3 4 3 0 4 1 0 3 2 1 4 4 1 3 2 3 3 3 3 1 0 3 0 4 3 1 0 4 0 4 4 1 2 0 0 4 1 3 3 3 0 2 2 1 1 2 3 4 1 2 72 29 1138 59 78 2398 95 5 1610 32 46 4176 36 99 8143 100 69 413 61 58 1595 9 9...
output:
13919 9039 12183 14028 13329 12072 10786 13408 10693 10661 12170 11759 10333 12396 11478 4580 11539 12073 12692 10455 18674 12942 11330 10757 15335 21490 11668 2322 10673 11049 11532 11308 8353 -1 12341 14285 11850 8993 11654 12808 8124 10795 24260 10965 14460 12766 -1 9076 10125 16724 -1 12235 1288...
result:
wrong answer 1st numbers differ - expected: '5109', found: '13919'