답안 #448092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
448092	2021-07-28T22:03:48 Z	training4usaco	악어의 지하 도시 (IOI11_crocodile)	C++11	컴파일 오류	0 ms	0 KB

crocodile

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 1000000009

struct Edge {
    int a, b, weight;

    Edge(int _a, int _b) : a(_a), b(_b) {

    }
};

#define mp make_pair
#define fi first
#define se second

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    // cout << n << " " << m << " " << k << endl;

    vector<Edge> edges;
    vector<vector<pair<int, int>>> adj(n);

    for(int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        // cout << x << " " << y << endl;

        edges.push_back(Edge(x, y));
    }

    for(int i = 0; i < m; ++i) {
        cin >> edges[i].weight;
    }

    // cout << "edges: " << endl;
    for(int i = 0; i < m; ++i) {
        // cout << edges[i].a << " " << edges[i].b << " " << edges[i].weight << endl;;
        adj[edges[i].a].push_back(mp(edges[i].b, edges[i].weight));
        adj[edges[i].b].push_back(mp(edges[i].a, edges[i].weight));
    }

    // for(int i = 0; i < n; ++i) {
    //     cout << i << ": ";
    //     for(int j = 0; j < adj[i].size(); ++j) {
    //         cout << "(" << adj[i][j].fi << ", " << adj[i][j].se << "); ";
    //     }
    //     cout << endl;
    // }

    vector<int> exits(k);

    for(int i = 0; i < k; ++i) {
        cin >> exits[i];
    }

    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    dist[0] = 0;
    visited[0] = true;
    priority_queue<int> pq;

    pq.push(0);

    while(!pq.empty()) {
        int curr = pq.top();
        pq.pop();

        int smallest_node = -1;
        int second_smallest_n = -1;
        int smallest_w = INF;
        int second_smallest_w = INF;

        for(auto next : adj[curr]) {
            if(!visited[next.fi]) {
                if(next.se <= smallest_w) {
                    second_smallest_w = smallest_w;
                    second_smallest_n = smallest_node;
                    smallest_w = next.se;
                    smallest_node = next.fi;
                }
                else if(next.se < second_smallest_w) {
                    second_smallest_w = next.se;
                    second_smallest_n = next.fi;
                }
            }
        }

        if(second_smallest_n == -1) {
            continue;
        }

        if(visited[second_smallest_n]) {
            continue;
        }
        // cout << "ssn: " << second_smallest_n << endl;
        visited[second_smallest_n] = true;
        dist[second_smallest_n] = dist[curr] + second_smallest_w;
        pq.push(second_smallest_n);
    }

    // for(int i = 0; i < n; ++i) {
    //     cout << dist[i] << endl;
    // }

    int answer = INF;

    for(int i = 0; i < k; ++i) {
        answer = min(answer, dist[exits[i]]);
    }

    cout << answer << endl;

    return 0;
}

Compilation message

/usr/bin/ld: /tmp/cclz1HER.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccmuShaV.o:crocodile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cclz1HER.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