QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356567#6523. Escape PlanNgTrung2217WA 594ms106092kbC++142.1kb2024-03-17 23:51:442024-03-17 23:51:44

Judging History

你现在查看的是最新测评结果

  • [2024-03-17 23:51:44]
  • 评测
  • 测评结果:WA
  • 用时:594ms
  • 内存:106092kb
  • [2024-03-17 23:51:44]
  • 提交

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();
    }
}

Details

Tip: Click on the bar to expand more detailed information

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'