제출 #1183045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183045		Erick_7314	악어의 지하 도시 (IOI11_crocodile)	C++20	컴파일 에러	0 ms	0 KiB

crocodile

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

struct Edge {
    int to;
    ll w;
};

struct Node {
    ll val;
    int id;
    bool operator>(const Node &other) const {
        return val > other.val;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Leer entrada
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<Edge>> adj(N);
    for (int i = 0; i < M; i++){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        // Añadimos corredores en ambos sentidos
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<bool> exitChamber(N, false);
    vector<int> exits(K);
    for (int i = 0; i < K; i++){
        cin >> exits[i];
        exitChamber[exits[i]] = true;
    }

    // f[u] es el tiempo garantizado para escapar desde u
    vector<ll> f(N, INF);
    // Para cada cámara, se mantienen best[u] y second[u]
    vector<ll> best(N, INF), second(N, INF);
    
    // Para cámaras de salida: f=0 y (best, second) no se usan.
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    for (int u = 0; u < N; u++){
        if (exitChamber[u]){
            f[u] = 0;
            pq.push({0, u});
        }
    }
    
    // Propagación al estilo Dijkstra (reverse dynamic programming)
    while (!pq.empty()){
        Node cur = pq.top();
        pq.pop();
        int u = cur.id;
        if (cur.val != f[u]) continue;
        // Para cada vecino v (con u como "hijo" en la ecuación)
        for (auto &edge : adj[u]) {
            int v = edge.to;
            // Evitamos modificar cámaras de salida (ya tienen f=0)
            if (exitChamber[v]) continue;
            ll candidate = edge.w + f[u];
            // Actualizamos la pareja (best[v], second[v]) con el valor candidato
            if (candidate < best[v]) {
                second[v] = best[v];
                best[v] = candidate;
            } else if (candidate < second[v] && candidate != best[v]) {
                second[v] = candidate;
            }
            // El valor garantizado en v es el segundo mejor
            if (second[v] < f[v]) {
                f[v] = second[v];
                pq.push({f[v], v});
            }
        }
    }
    
    // f[0] contiene la solución: el menor tiempo T en el que existe un buen plan
    cout << f[0] << "\n";
    return 0;
}

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

/usr/bin/ld: /tmp/ccrD5sWs.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccZHzYMt.o:crocodile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccrD5sWs.o: in function `main':
grader.cpp:(.text.startup+0x36): undefined reference to `travel_plan(int, int, int (*) [2], int*, int, int*)'
collect2: error: ld returned 1 exit status