Submission #448093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448093	2021-07-28T22:08:11 Z	training4usaco	Crocodile's Underground City (IOI11_crocodile)	C++11	Compilation error	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 trave_plan(int n, int m, vector<vector<int>> edges, vector<int> weights, int k, vector<int> exits) {
    // cout << n << " " << m << " " << k << endl;

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

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

    // 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> 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

crocodile.cpp: In function 'int trave_plan(int, int, std::vector<std::vector<int> >, std::vector<int>, int, std::vector<int>)':
crocodile.cpp:23:18: error: declaration of 'std::vector<Edge> edges' shadows a parameter
   23 |     vector<Edge> edges;
      |                  ^~~~~
crocodile.cpp:20:50: note: 'std::vector<std::vector<int> > edges' previously declared here
   20 | int trave_plan(int n, int m, vector<vector<int>> edges, vector<int> weights, int k, vector<int> exits) {
      |                              ~~~~~~~~~~~~~~~~~~~~^~~~~
crocodile.cpp:29:21: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<Edge>, Edge>::value_type' {aka 'Edge'} and 'int')
   29 |         adj[edges[i][0]].push_back(mp(edges[i][1], weights[i]));
      |                     ^
crocodile.cpp:29:47: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<Edge>, Edge>::value_type' {aka 'Edge'} and 'int')
   29 |         adj[edges[i][0]].push_back(mp(edges[i][1], weights[i]));
      |                                               ^
crocodile.cpp:30:21: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<Edge>, Edge>::value_type' {aka 'Edge'} and 'int')
   30 |         adj[edges[i][1]].push_back(mp(edges[i][0], weights[i]));
      |                     ^
crocodile.cpp:30:47: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<Edge>, Edge>::value_type' {aka 'Edge'} and 'int')
   30 |         adj[edges[i][1]].push_back(mp(edges[i][0], weights[i]));
      |                                               ^