제출 #1300126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300126		red_souls	Relay Marathon (NOI20_relaymarathon)	C++20	0 / 100	30 ms	7380 KiB

RelayMarathon

#include <bits/stdc++.h>
#define ll long long
#define task "RELAYMARATHON"
using namespace std;

const int N = 1e5 + 16;
const ll INF = 1e18;
int n, m, K, u, v, a[N];
ll w, result;
vector < pair <int, ll> > adj[N];

namespace sub4 {

    ll d[N];
    priority_queue < pair <ll, int>, vector < pair <ll, int> >, greater < pair <ll, int> > > pq;

    void dijkstra(int k) {
        for (int i = 1; i <= n; i++) {
            d[i] = INF;
        }
        d[k] = 0;
        pq.push({d[k], k});
        while (!pq.empty()) {
            pair <ll, int> top = pq.top();
            pq.pop();
            ll dist = top.first;
            int u = top.second;
            if (dist > d[u]) {
                continue;
            }
            for (auto v : adj[u]) {
                int vertex = v.first;
                ll value = v.second;
                if (d[vertex] > dist + value) {
                    d[vertex] = dist + value;
                    pq.push({d[vertex], vertex});
                }
            }
        }
    }

    int s1 = -1, e1 = -1, s2 = -1, e2 = -1;

    void solve() {
        dijkstra(a[1]);
        for (int i = 1; i <= K; i++) {
            if (a[i] == a[1]) {
                continue;
            }
            if (s1 == -1 || d[s1] > d[a[i]]) {
                s1 = a[i];
            }
        }
        dijkstra(s1);
        for (int i = 1; i <= K; i++) {
            if (a[i] == s1) {
                continue;
            }
            if (e1 == -1 || d[e1] > d[a[i]]) {
                e1 = a[i];
            }
        }
        result += d[e1];

        int root = -1;
        for (int i = 1; i <= K; i++) {
            if (a[i] == s1 || a[i] == e1) {
                continue;
            }
            root = a[i];
            break;
        }

        dijkstra(root);
        for (int i = 1; i <= K; i++) {
            if (a[i] == s1 || a[i] == e1) {
                continue;
            }
            if (s2 == -1 || d[s2] > d[a[i]]) {
                s2 = a[i];
            }
        }
        dijkstra(s2);
        for (int i = 1; i <= K; i++) {
            if (a[i] == s1 || a[i] == e1) {
                continue;
            }
            if (a[i] == s2) {
                continue;
            }
            if (e2 == -1 || d[e2] > d[a[i]]) {
                e2 = a[i];
            }
        }
        result += d[e2];

        cout << result;
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n >> m >> K;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i = 1; i <= K; i++) {
        cin >> a[i];
    }
    sub4 :: solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58