제출 #1196221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196221		GoBananas69	Cyberland (APIO23_cyberland)	C++20	0 / 100	65 ms	5444 KiB

cyberland

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using std::vector;
using std::pair;
using std::priority_queue;

vector<vector<pair<int, int>>> adj;

int dijkstra(int s, int h) {
    int n = adj.size();
    vector<int> dist(n, 1e9);
    vector<bool> vis(n, false);
    dist[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &p: adj[u]) {
            int v = p.first;
            int w = p.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist[h];
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    adj.resize(n);
    for (int i = 0; i<m; ++i) {
        int u = x[i], v = y[i], w = c[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    return dijkstra(0, h);
    // return dist[h];
}

// int main() {
// 	int res = solve(3, 1, {-1, 0, 0}, {{1, 2}});
// 	cout << res << '\n';
// }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3