QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#356567 | #6523. Escape Plan | NgTrung2217 | WA | 594ms | 106092kb | C++14 | 2.1kb | 2024-03-17 23:51:44 | 2024-03-17 23:51:44 |
Judging History
answer
#include <bits/stdc++.h>
#define task ""
#define ff first
#define ss second
using namespace std;
using ld = long double;
using ull = unsigned long long;
using ll = long long;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
const char el = '\n';
const char sp = ' ';
const ll inf = 1e18;
const ll maxN = 1e6 + 5;
int n, m, k;
struct Tedge
{
ll u, v, w;
} e[maxN];
vector <int> adj[maxN];
ll f[maxN], d[maxN], vis[maxN];
struct Titem
{
ll v, w;
bool operator < (const Titem& o) const
{
return o.w < w;
}
bool valid() const
{
return d[v] == w;
}
};
bool relax(int u, int v, ll w)
{
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;
return 1;
}
return 0;
}
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int t;
cin >> t;
while(t--)
{
cin >> n >> m >> k;
fill(d, d + 1 + n, inf);
priority_queue <Titem> pq;
for (int i = 1;i <= k;++i)
{
int x;
cin >> x;
d[x] = 0;
pq.push({x, 0});
}
for (int i = 1;i <= n;++i)
cin >> f[i];
for (int i = 1;i <= m;++i)
{
cin >> e[i].u >> e[i].v >> e[i].w;
adj[e[i].u].push_back(i);
adj[e[i].v].push_back(i);
}
while(!pq.empty())
{
Titem item = pq.top();
pq.pop();
int u = item.v;
if (f[u] > 0 && d[u] > 0)
{
f[u]--;
continue;
}
if (vis[u]) continue;
vis[u] = 1;
d[u] = item.w;
for (int i : adj[u])
{
int v = e[i].u ^ e[i].v ^ u;
pq.push({v, d[u] + e[i].w});
}
}
cout << (d[1] == inf ? -1 : d[1]) << el;
for (int i = 1;i <= n;++i)
adj[i].clear();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 32536kb
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: 594ms
memory: 106092kb
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:
5109 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 2nd numbers differ - expected: '1021', found: '-1'