제출 #1150713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150713		DON_F	악어의 지하 도시 (IOI11_crocodile)	C++20	100 / 100	354 ms	72988 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define L(i, b, e) for (int i = b; i < e; ++i)
#define R(i, b, e) for (int i = b; i >= e; --i)
#define pb emplace_back
#define vi vector<int>
#define sz(x) ((int) x.size())
const int N = 1e6 + 7, Mx = 1e9 + 9;

int travel_plan(int n, int m, int e[][2], int w[], int k, int p[]){
    vector<pair<int, ll>> g[n];
    L(i, 0, m){
        g[e[i][0]].pb(e[i][1], w[i]);
        g[e[i][1]].pb(e[i][0], w[i]);
    }
    vector<pair<ll, ll>> dis(n, {1LL * Mx * Mx, 1LL * Mx * Mx});
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    L(i, 0, k){
        dis[p[i]].first = 0;
        pq.push({0, p[i]});
    }
    vector<bool> vis(n);
    while (!pq.empty()){
        auto [d, x] = pq.top();
        pq.pop();
        if (vis[x])continue;
        vis[x] = true;
        for (auto &[b, t] : g[x]){
            if (d + t < dis[b].second){
                swap(dis[b].first, dis[b].second);
                dis[b].second = d + t;
                if (dis[b].first != 1LL * Mx * Mx){
                    pq.push({dis[b].first, b});
                }
            }else if (d + t < dis[b].first){
                dis[b].first = d + t;
                pq.push({dis[b].first, b});
            }
        }
    }
    assert(dis[0].first != 1LL * Mx * Mx);
    return dis[0].first;
}

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