QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#368525#6523. Escape PlankabuuRE 1ms3548kbC++202.5kb2024-03-27 11:01:472024-03-27 11:01:48

Judging History

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

  • [2024-03-27 11:01:48]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3548kb
  • [2024-03-27 11:01:47]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define debug cerr << 6666 << endl;
#pragma GCC optimize(2)
using namespace std;
const ll mod = 998244353;
const ll N = 1e6 + 100;
const ll inf = 1e18;
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> e(k + 1);
    for (int i = 1; i <= k; i++)
        cin >> e[i];
    vector<int> d(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    vector<vector<array<int, 3>>> g(n + 1);
    vector<vector<ll>> dis(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({ v, w, dis[u].size() + 1 });
        g[v].push_back({ u, w, dis[v].size() + 1 });
        dis[u].push_back(inf);
        dis[v].push_back(inf);
    }
    for (int i = 1; i <= n; i++)
        dis[i].push_back(1e18);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    for (int i = 1; i <= k; i++) {
        q.push({ 0, e[i] });
        for (int j = 1; j < dis[e[i]].size(); j++)
            dis[e[i]][j] = 0;
    }
    auto monst = d;
    // cerr << 666;
    vector<bool> vis(n + 1);
    while (q.size()) {
        auto [far, u] = q.top();
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto [v, w, id] : g[u]) {
            // if (dis[v][cur] > far + 1ll * u) {
            if (dis[v][id] == inf) {
                monst[v]--;
            }
            dis[v][id] = min(dis[v][id], far + 1ll * w);
            // cerr << v << " " << far + w << '\n';
            if (monst[v] <= 0) {
                // cerr << 666;
                auto tmp = dis[v];
                sort(tmp.begin() + 1, tmp.end());
                // for (auto x : tmp)
                //     cerr << x << " ";
                // cerr << "\n";
                if (tmp[d[v] + 1] != inf && !vis[v]) {
                    // cerr << v << " " << tmp[d[v] + 1] << "  \n";
                    q.push({ tmp[d[v] + 1], v });
                }
            }
            // }
        }
    }
    auto tmp = dis[1];
    sort(tmp.begin() + 1, tmp.end());
    // for (auto x : tmp)
    // cerr << x << " ";
    if (d[1] + 1 == dis[1].size() || tmp[d[1] + 1] == inf) {
        cout << -1 << '\n';
    } else {
        cout << tmp[d[1] + 1] << '\n';
    }
}
/*
 */
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);
    int T_T = 1;
    std::cin >> T_T;
    while (T_T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3548kb

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
Runtime Error

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:


result: