| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 96302 | 2019-02-08T09:33:25 Z | figter001 | Crocodile's Underground City (IOI11_crocodile) | C++14 | 0 ms | 0 KB |
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+50;
vector<pair<int,ll>> g[maxn];
pair<ll,ll> cost[maxn];
int n;
bool e[maxn],vis[maxn];
void dij(){
priority_queue<pair<ll,int>> q;
for(int i=0;i<n;i++)
cost[i] = {1e18,1e18};
for(int i=0;i<n;i++)
if(e[i]){
cost[i] = {0,0};
q.push({0,i});
}
while(q.size()){
int u = q.top().second;
ll cst = -q.top().first;
q.pop();
if(vis[u])continue;
vis[u] = 1;
for(pair<int,ll> cur : g[u]){
int v = cur.first;
ll w = cur.second;
ll ncst = cst + w;
if(cost[v].second <= ncst)continue;
if(ncst < cost[v].first){
cost[v].second = cost[v].first;
cost[v].first = ncst;
}else if(ncst < cost[v].second){
cost[v].second = ncst;
}
q.push({-cost[v].second,v});
}
}
}
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];
int v = R[i][1];
int w = L[i];
g[u].push_back({v,w});
g[v].push_back({u,w});
}
for(int i=0;i<K;i++)
e[P[i]] = 1;
dij();
return cost[0].second;
}