제출 #787149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787149		gagik_2007	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	409 ms	73768 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
vector<pair<ll,ll>>g[N];
int used[N];

int travel_plan(int NN, int MM, int R[][2], int L[], int KK, int P[]){
    n=NN;
    m=MM;
    k=KK;
    for(ll i=0;i<m;i++){
        // cout<<R[i][0]<<" "<<R[i][1]<<endl;
        g[R[i][0]].push_back(make_pair(R[i][1],L[i]));
        g[R[i][1]].push_back(make_pair(R[i][0],L[i]));
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    vector<ll>mn(n+1,INF),smn(n+1,INF);
    // cout<<mn[0]<<" "<<smn[0]<<endl;
    for(ll i=0;i<k;i++){
        q.push(make_pair(0,P[i]));
        mn[P[i]]=smn[P[i]]=0;
    }
    while(!q.empty()){
        ll v=q.top().ss;
        ll w=q.top().ff;
        // cout<<v<<" "<<w<<endl;
        // cout<<mn[v]<<" "<<smn[v]<<endl<<endl;
        q.pop();
        if(smn[v]==w){
            // if(v==320){
            //     cout<<"Qnnarkum enq 320in: "<<w<<endl;
            // }
            // if(used[v])cout<<v<<": "<<used[v]<<"->"<<w<<endl;
            used[v]=w;
            for(pii x:g[v]){
                ll to=x.ff;
                ll dist=x.ss;
                // cout<<v<<" "<<to<<" "<<dist<<endl;
                // cout<<mn[to]<<" "<<smn[v]<<endl;
                // cout<<endl;
                if(mn[to]>smn[v]+dist){
                    // if(to==320){
                    //     cout<<"320y yngnelu a queue-i mej (hima: "<<smn[to]<<")"<<endl;
                    // }
                    bool etas=!(smn[to]==mn[to]);
                    smn[to]=mn[to];
                    mn[to]=smn[v]+dist;
                    if(smn[to]!=INF&&etas)
                    q.push(make_pair(smn[to],to));
                    // if(to==320){
                    //     cout<<"320y yngav queue-i mej 1: "<<smn[to]<<endl;
                    // }
                }
                else if(smn[to]>smn[v]+dist){
                    // if(to==320){
                    //     cout<<"320y yngnelu a queue-i mej (hima: "<<smn[to]<<")"<<endl;
                    // }
                    smn[to]=smn[v]+dist;
                    q.push(make_pair(smn[to],to));
                    // if(to==320){
                    //     cout<<"320y yngav queue-i mej 2: "<<smn[to]<<endl;
                    // }
                }
            }
        }
    }
    return smn[0];
}

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