Submission #562629

#	Time	Username	Problem	Language	Result	Execution time	Memory
562629		Iwanttobreakfree	Crocodile's Underground City (IOI11_crocodile)	C++98	0 / 100	1 ms	212 KiB

crocodile

#include <iostream>
#include <vector>
#include <queue>
#include "crocodile.h"
using namespace std;
typedef long long ll;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector<pair<ll,ll>> d(N,{1e18,1e18});
    vector<vector<pair<int,int>>> g(N,vector<pair<int,int>>());
    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<ll,int>> pq;
    for(int i=0;i<K;i++)pq.push({0,P[i]});
    while(pq.empty()){
        ll dist=-pq.top().first,u=pq.top().second;
        pq.pop();
        if(dist>d[u].second)continue;
        for(auto v:g[u]){
            if(dist+v.second<d[v.first].first){
                d[v.first].second=d[v.first].first;
                d[v.first].first=dist+v.second;
                pq.push({-d[v.first].second,v.first});
            }
            if(dist+v.second<d[v.first].second){
                d[v.first].second=dist+v.second;
                pq.push({-d[v.first].second,v.first});
            }
        }
    }
    return d[0].second;
}

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