Submission #391687

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

crocodile

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

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

void update(LL &x,ll 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;
}

ll n,m,R[N][2],lens[N],k,a[N];
/*
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>m>>k;
    for (ll i = 0;i < m;i++) cin>>R[i][0]>>R[i][1]>>lens[i];
    for (ll i = 0;i < k;i++) cin>>a[i];
    cout<<travel_plan(n,m,R,lens,k,a);
}
*/

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