Submission #391691

#	Time	Username	Problem	Language	Result	Execution time	Memory
391691		cpp219	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	2716 KiB

crocodile

#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<long long,long long> LL;
const ll N = 1e5 + 9;
const long long inf = 1e16 + 7;
#include "crocodile.h"
vector<ll> vec;
vector<LL> g[N];
LL d[N];
ll ans;
struct Node{
    long long cur,w1,w2;
};

bool operator < (Node a,Node b){
    return a.w2 > b.w2;
}
priority_queue<Node> pq;

void update(LL &x,long long y){
    if (x.fs >= y) x.sc = x.fs,x.fs = y;
    else if (x.sc > y) x.sc = y;
}

void Dij(ll n){
    for (ll i = 0;i < n;i++) d[i] = {inf,inf};
    for (auto i : vec) d[i] = {0,0},pq.push({i,0,0});
    while(!pq.empty()){
        Node t = pq.top(); pq.pop();
        ll u = t.cur,cost = t.w2;
        for (auto i : g[u]){
            ll v = i.fs,L = i.sc;
            if (d[v].sc > cost + L){
                update(d[v],cost + L); pq.push({v,d[v].fs,d[v].sc});
            }
        }
    }
    ans = d[0].sc;
}

ll travel_plan(ll n,ll m,ll R[][2],ll lens[],ll k,ll a[]){
    for (ll i = 0;i < k;i++) vec.push_back(a[i]);
    for (ll i = 0;i < m;i++){
        ll u = R[i][0],v = R[i][1],L = lens[i];
        g[u].push_back({v,L}); g[v].push_back({u,L});
    }
    Dij(n); return ans;
}

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