Submission #372853

#	Time	Username	Problem	Language	Result	Execution time	Memory
372853		ntabc05101	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1447 ms	93800 KiB

crocodile

#include<bits/stdc++.h>
using namespace std;

int64_t travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {        
        vector< pair<int, int> > adjList[n];
        for (int i = 0; i < m; i++) {
                adjList[r[i][0]].push_back({r[i][1], l[i]});
                adjList[r[i][1]].push_back({r[i][0], l[i]});
        }

        priority_queue< pair<int64_t, int> > pq;
        vector<int64_t> distList[n];
        for (int i=0; i<k; ++i) {
                distList[p[i]].push_back(0);
                pq.push({-0, p[i]});
        }

        while (!pq.empty()) {
                int64_t cdist = -pq.top().first;
                int cvertex = pq.top().second;

                //cout << cdist << " " << cvertex << "\n";
                pq.pop();

                if (distList[cvertex].size() > 1) continue;
                distList[cvertex].push_back(cdist);
                if (distList[cvertex].size() == 2) {
                        for (pair<int, int>& to: adjList[cvertex]) {
                                pq.push({-(cdist+to.second), to.first});
                        }
                }
        }

        return distList[0][1];
}

/*int main() {
        ios_base::sync_with_stdio(0); cin.tie(0);

        int n, m, k; cin >> n >> m >> k;
        int r[m][2], l[m];
        for (int i = 0; i < m; i++) {
                cin >> r[i][0] >> r[i][1] >> l[i];
        }
        int p[k];
        for (int i = 0; i < k; i++) {
                cin >> p[i];
        }

        cout << travel_plan(n, m, r, l, k, p) << "\n";

        return 0;
}*/

/*
5 4 3
0 1
0 2
3 2
2 4
2 3 1 4
1 3 4
*/

/*
5 7 2
0 2
0 3
3 2
2 1
0 1
0 4
3 4
4 3 2 10 100 7 9
1 3
*/

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11