Submission #1216546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216546		kiennguyendinh	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	2 ms	4928 KiB

crocodile

#include <bits/stdc++.h> 
#include "crocodile.h"
using namespace std;    
int n, m, k;
bool spec[100001]; 
vector<pair<int, int>> g[100001], sp[100001];
array<int, 2> dist[100001];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N, m = M, k = K; 
    for(int i = 0;i < n;i++){
        dist[i] = {(int)1e9, (int)1e9};
    }
    for(int i = 0;i < m;i++){
        g[R[i][0]].push_back({R[i][1], L[i]});
        g[R[i][1]].push_back({R[i][0], L[i]}); 
    } 
    priority_queue<pair<int, int>> Q;
    for(int i = 0;i < k;i++) {
        Q.push(make_pair(0, P[i]));
        dist[P[i]] = {0, 0};
    }   
    while(!Q.empty()) {
        pair<int, int> x = Q.top();
        int w = Q.top().first,u = Q.top().second;
        Q.pop();
        w *= -1;
        if(dist[u][1] < w) continue;
        for(pair<int,int> v : g[u]) {
            if(w + v.second < dist[v.first][0]) {
                if(dist[v.first][0] < dist[v.first][1]) {
                    Q.push(make_pair(-dist[v.first][0], v.first));
                }
                dist[v.first][1] = dist[v.first][0];
                dist[v.first][0] = x.first + v.second;
            } else if(x.first + v.second < dist[v.first][1]) {
                dist[v.first][1] = x.first + v.second;
                Q.push(make_pair(-dist[v.first][1], v.first));
            }
        }
    }
    return dist[0][1];
}  

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