Submission #64085

#	Time	Username	Problem	Language	Result	Execution time	Memory
64085		zubec	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1597 ms	105308 KiB

crocodile

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

const int N = 100100;

vector <pair<int, int> > g[N];

int n, pr[N];

long long d[N][2];

map<int, int> blockd[N];


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N;
    for (int i = 0; i < M; i++){
        int u = R[i][0]+1, v = R[i][1]+1;
        g[u].push_back({v, L[i]});
        g[v].push_back({u, L[i]});
    }
    set<pair<long long, int> > q;
    for (int i = 1; i <= n; i++)
        d[i][0] = d[i][1] = 1e15;
    for (int i = 0; i < K; i++){
        int v = P[i]+1;
        d[v][1] = 0;
        d[v][0] = 0;
        q.insert({0, v});
    }
    while(!q.empty()){
        int v = q.begin()->second;
        //cout << v-1 << ' ' << d2[v] << endl;
        q.erase(q.begin());
        for (int i = 0; i < g[v].size(); i++){
            int to = g[v][i].first, len = g[v][i].second;
            if (d[v][1] + len < d[to][0]){
                q.erase({d[to][1], to});
                d[to][1] = d[to][0];
                d[to][0] = d[v][1] + len;
                q.insert({d[to][1], to});
            } else
            if (d[v][1] + len < d[to][1]){
                q.erase({d[to][1], to});
                d[to][1] = d[v][1] + len;
                q.insert({d[to][1], to});
            }
        }
    }
    long long mn = d[1][1];
    if (mn == 1e15)
        mn = -1;
    return mn;

}

/**

13 12 9
0 2 4
0 1 1
0 3 11
2 8 13
2 9 23
2 7 3
1 5 7
1 6 15
1 4 11
3 10 3
3 11 1
3 12 2
8 9 7 5 6 12 11 10 4
13

*/

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:36:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++){
                         ~~^~~~~~~~~~~~~

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