제출 #1252215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252215		lambd47	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	321 ms	43188 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define sz(v) ((int)v.size())
#define all(v) (v).begin(),(v).end()
#define ll long long

int travel_plan(int n, int m, int R[][2], int len[], int ps, int P[])
{
    vector<vector<int>> adj(n);
    L(i,0,m-1){
        auto [a,b]=R[i];
        adj[a].push_back(i);
        adj[b].push_back(i);
    }

    const ll MOD=1e9;
    vector<pair<ll,ll>> dp(n,{MOD,MOD});

    priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
    L(i,0,ps-1){
        dp[P[i]]={0,0};
        pq.push({0,0,P[i]});
    }
    
    while(!pq.empty()){
        auto [a,b,v]=pq.top();
        pq.pop();
        if(make_pair(a,b)!=dp[v])continue;

        for(auto e: adj[v]){
            int vai=R[e][0]^R[e][1]^v;
            ll w=len[e];
            if(dp[vai].second>a+w){
                dp[vai].first=dp[vai].second;
                dp[vai].second=a+w;
                pq.push({dp[vai].first,dp[vai].second,vai});
            }
            else if(dp[vai].first>a+w){
                dp[vai].first=a+w;
                pq.push({dp[vai].first,dp[vai].second,vai});
            }
        }

    }
    /*
    L(i,0,n-1){
        cout<<dp[i].first<<" "<<dp[i].second<<"\n";
    }
    */ return dp[0].first;





}

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