QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#360170 | #6523. Escape Plan | Djangle162857 | WA | 734ms | 99784kb | C++20 | 1.6kb | 2024-03-21 14:11:19 | 2024-03-21 14:11:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3fll;
const int N = 1000005;
int t, n, m, k;
struct Edge {
int v, w;
bool operator<(const Edge &rsh) const
{
return w > rsh.w;
}
};
vector<Edge> g[N];
int dp[N], d[N], e[N];
priority_queue<Edge> q;
priority_queue<int> mn[N]; //求解第d[i]+1小的数,用一个大根堆
signed main()
{
// cout << "ok" << endl;
cin >> t;
while (t--) {
cin >> n >> m >> k;
//初始化
while (q.size())
q.pop();
for (int i = 1; i <= n; i++)
dp[i] = inf;
for (int i = 1; i <= n; i++)
g[i].clear();
for (int i = 1; i <= n; i++)
while (mn[i].size())
mn[i].pop();
for (int i = 1; i <= n; i++)
dp[i] = inf;
for (int i = 1; i <= k; i++) {
scanf("%lld", &e[i]);
q.push((Edge){e[i], 0});
}
for (int i = 1; i <= n; i++) {
scanf("%lld", &d[i]);
d[i]++;
}
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
g[u].push_back((Edge){v, w});
g[v].push_back((Edge){u, w});
}
while (q.size()) {
int v = q.top().v, _dp = q.top().w;
q.pop();
if (dp[v] < inf)
continue;
dp[v] = _dp;
for (int i = 0; i < g[v].size(); i++) {
int u = g[v][i].v, w = g[v][i].w;
if (dp[u] < inf)
continue;
// cout<<"1"<<endl;
if (mn[u].size() < d[u])
mn[u].push(w + _dp);
if (mn[u].size() == d[u])
q.push((Edge){u, mn[u].top()});
}
}
if (dp[1] < inf)
cout << dp[1] << endl;
else
cout << -1 << endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 35036kb
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: 734ms
memory: 99784kb
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:
8619 1021 9557 7664 5555 7413 8935 7487 9433 9832 11262 9597 9165 12162 9820 12363 11265 9812 10989 4923 13199 12942 8185 10757 14101 17965 10003 2322 5387 9734 10780 11427 4157 -1 10207 6265 7250 8948 10626 10529 4253 9173 21843 10625 9100 11884 -1 986 4335 11773 -1 3166 7387 13886 13998 5770 11188...
result:
wrong answer 1st numbers differ - expected: '5109', found: '8619'