답안 #989697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989697	2024-05-28T15:06:24 Z	vjudge2	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	636 ms	94984 KB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>

const ll INF = 1e18;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<vector<pii>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
    vector<int> cnt(N, 0);
    vector<ll> di(N, INF);
    for (int i = 0; i < K; i++) {
        cnt[P[i]] = 1, di[P[i]] = 0;
        q.push({0, P[i]});
    }
    while (!q.empty()) {
        auto [dist, u] = q.top();
        q.pop();
        cnt[u]++;
        if (cnt[u] == 2) {
            di[u] = dist;
            for (auto& [v, w] : adj[u]) {
                q.push({di[u] + w, v});
            }
        }
    }
    return di[0];
}

Subtask #1

46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4552 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct

Subtask #2

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4552 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	4 ms	4956 KB	Output is correct
10	Correct	2 ms	4444 KB	Output is correct
11	Correct	2 ms	4700 KB	Output is correct
12	Correct	6 ms	5556 KB	Output is correct
13	Correct	5 ms	5588 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4440 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4552 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	4 ms	4956 KB	Output is correct
10	Correct	2 ms	4444 KB	Output is correct
11	Correct	2 ms	4700 KB	Output is correct
12	Correct	6 ms	5556 KB	Output is correct
13	Correct	5 ms	5588 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	633 ms	89852 KB	Output is correct
17	Correct	58 ms	16208 KB	Output is correct
18	Correct	83 ms	17172 KB	Output is correct
19	Correct	636 ms	94984 KB	Output is correct
20	Correct	454 ms	82612 KB	Output is correct
21	Correct	32 ms	9308 KB	Output is correct
22	Correct	438 ms	47264 KB	Output is correct