Submission #723990

#	Time	Username	Problem	Language	Result	Execution time	Memory
723990		urosk	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	7 ms	2772 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define ll long long
#define endl '\n'
#define pll pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
#define llinf 1000000000LL
using namespace std;
#define maxn 100005
 
ll n,m,k;
vector<pll> g[maxn];
ll d[maxn][2];
bool ok[maxn];
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N;
    m = M;
    k = K;
    for(ll i = 0;i<m;i++){
        ll x = R[i][0],y = R[i][1];
        x++; y++;
        ll w = L[i];
        g[x].pb({y,w});
        g[y].pb({x,w});
    }
    priority_queue<pll> pq;
    for(ll i = 1;i<=n;i++) d[i][0] = d[i][1] = llinf;
    for(ll i = 1;i<=k;i++){
        ll x = P[i-1] + 1;
        ok[x] = 1;
        d[x][0] = d[x][1] = 0;
        pq.push({0,x});
    }
    while(pq.size()){
        pll p = pq.top();
        pq.pop();
        ll u = p.sc;
        ll cur = -p.fi;
        if(cur>d[u][1]) continue;
        if(!ok[u]&&cur==d[u][0]) continue;
        for(pll p : g[u]){
            ll s = p.fi;
            ll w = p.sc;
            if(cur+w<d[s][0]){
                d[s][1] = d[s][0];
                d[s][0] = cur + w;
                pq.push({-d[s][0],s});
            }else if(cur+w<d[s][1]){
                d[s][1] = cur + w;
                pq.push({-d[s][1],s});
            }
        }
    }
    for(ll i = 1;i<=n;i++) cerr<<d[i][0]<< " "<<d[i][1]<<endl;
    return d[1][1];
}
/**
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
 
 
**/

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