Submission #164344

#	Time	Username	Problem	Language	Result	Execution time	Memory
164344		dantoh000	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	793 ms	61428 KiB

crocodile

#include <bits/stdc++.h>
//#include "crocodile.h"
using namespace std;
typedef pair<int,int> ii;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    vector<ii> adjlist[N];
    for (int i = 0; i < M; i++){
        adjlist[R[i][0]].push_back(ii(R[i][1],L[i]));
        adjlist[R[i][1]].push_back(ii(R[i][0],L[i]));
    }
    priority_queue<ii,vector<ii>, greater<ii> > pq;
    int bist[N], dist[N];
    memset(bist,-1,sizeof(bist));
    memset(dist,-1,sizeof(dist));
    for (int i = 0; i < K; i++){
        dist[P[i]] = 0;
        pq.push(ii(0,P[i]));
    }
    while (pq.size()){
        ii cur = pq.top(); pq.pop();
        int d = cur.first, u = cur.second;
        if (dist[u] < d) continue;
        //printf("%d %d\n",d,u);
        for (auto v : adjlist[u]){
            if (bist[v.first] == -1){
                bist[v.first] = v.second + dist[u];
            }
            else{
                if (dist[v.first] == -1 || dist[v.first] > max(dist[u]+v.second,bist[v.first])){
                    dist[v.first] = max(dist[u]+v.second,bist[v.first]);
                    pq.push(ii(dist[v.first],v.first));
                }
                bist[v.first] = min(bist[v.first],dist[u]+v.second);
            }
        }
    }
    return dist[0];
}

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