QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356568#6523. Escape PlanNgTrung2217WA 4ms34288kbC++142.1kb2024-03-17 23:53:482024-03-17 23:53:49

Judging History

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

  • [2024-03-17 23:53:49]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:34288kb
  • [2024-03-17 23:53:48]
  • 提交

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 w < o.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: 0
Wrong Answer
time: 4ms
memory: 34288kb

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:

2
-1

result:

wrong answer 1st numbers differ - expected: '4', found: '2'