제출 #1191679

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

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
#define pb push_back
#define lint long long int
using namespace std;

int _n, _m, _k;
vector<bool> is_exit;
vector<vector<pair<int, int>>> edge;
int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
    _n=n; _m=m; _k=k;

    edge.resize(n);
    for (int i = 0; i < m; i ++) {
        edge[r[i][0]].pb({r[i][1], l[i]});
        edge[r[i][1]].pb({r[i][0], l[i]});
    }

    is_exit.resize(n, false);
    for (int i = 0; i < k; i ++) {
        is_exit[p[i]] = true;
    }

    vector<int> visited(n, 0);
    vector<pair<int, int>> dis(n, {1e9, 1e9});
    priority_queue<pair<int, pair<int, int>>> q;
    
    // for (int i = 0; i < k ; i ++) {
    //     for (auto [v, w] : edge[p[i]]) {
    //         q.push({-w, {v, p[i]}});
    //     }
    // }

    int MN_V = 1E9, MN_W = 1E9;
    for (auto [v, w] : edge[0]) {
        if (w < MN_W) {
            if (MN_V != 1E9) q.push({-MN_W, {MN_V, 0}});
            MN_W = w; MN_V = v;
        }
        else {
            q.push({-w, {v, 0}});
        }
    }
    
    while (!q.empty()) {
        int w = -q.top().first;
        int v = q.top().second.first, par = q.top().second.second;
        q.pop();
        // cout << w << " " << v << " " << par << endl;
        if (visited[v] > 2) {continue;}
        visited[v] ++;

        if (is_exit[v]) {
            // cout << "EXXXIIIITTTTT: " << v << " " << w << " " << par << endl;
            return w;
            // break;
        }

        if (w < dis[v].first) {
            dis[v].second = dis[v].first;
            dis[v].first = w;
        }
        else if (w < dis[v].second) {
            dis[v].second = w;    
        }
        int mn_v = 1e9, mn_w = 1e9, par_mn_v = 1e9;
        for (auto [new_v, new_w] : edge[v]) {
            // cout << " :: " << new_v << " " << new_w << endl;
            if (new_v == par) continue;
            

            
            // if (visited[new_v] < 2) {
                if (new_w+w < mn_w) {
                    // cout << ":1 -- " << new_w << " " << w << " " << mn_w << endl;
                    if (mn_v != 1e9) {q.push({-mn_w, {mn_v, par_mn_v}});}
                    mn_v = new_v; mn_w = new_w + w; par_mn_v = v;
                    // cout << "mn_v: " << mn_v << " mn_w: " << mn_w << " par_mn_v: " << par_mn_v << endl;
                }
                else {
                    // cout << ":2" << endl;
                    q.push({-(new_w+w), {new_v, v}});
                }
            // }
        }

    }

    // for (int i = 0; i < n; i ++) {
    //     cout << "i=" << i << ": " << dis[i].first << " " << dis[i].second << endl;
    // }

    // vector<bool> visited(n, false);
    // vector<pair<int, int>> dis(n, {1e9, 1e9});
    // priority_queue<pair<int, int>> q;
    // q.push({0, 0});
    // visited[0] = true;

    // while(!q.empty()) {
    //     int w = -q.top().first, v = q.top().second;
    //     q.pop();

    //     int mn_v=1e9, mn_w=1e9, next_is_exit = false;
    //     // if this node has one or more exit => block the smallest exit, push others
    //     // if this node has no exit => block the smallest one
    //     int exit_cnt = 0;
    //     pair<int, int> min1_exit = {1e9, 1e9}, min2_exit = {1e9, 1e9};
    //     for (auto [new_v, new_w] : edge[v]) {
    //         if (visited[new_v]) continue;

    //         if (is_exit[new_v]) {
    //             exit_cnt ++;
    //             if (exit_cnt == 1) {
    //                 // found the first exit, the nodes that is blocked previously can be push.
    //                 if (mn_v != 1e9) q.push({-mn_w, mn_v});
    //             }
    //             if (new_w + w < min1_exit.second) {
    //                 min2_exit = min1_exit;
    //                 min1_exit = {new_v, new_w + w};
    //             }
    //             else if (new_w + w < min2_exit.second) {
    //                 min2_exit = {new_v, new_w + w};
    //             }
    //         }
    //         else {
    //             if (exit_cnt == 0) {
    //                 // no exit found until now
    //                 // need to check if this node has smaller w
    //                 if (new_w + w < mn_w) {
    //                     if (mn_v != 1e9) q.push({-mn_w, mn_v});
    //                     mn_w = new_w + w;
    //                     mn_v = new_v;
    //                 }
    //                 else {
    //                     q.push({-(new_w+w), new_v});
    //                 }
    //             }
    //             else if (exit_cnt == 1) {
    //                 q.push({-(new_w+w), new_v});
    //             }
    //             // else if exit_cnt > 1, no need to push, already found a shortest path
    //         }
    //     }

    //     if (exit_cnt > 1) {
    //         dis[v] = min2_exit.second;
    //     }
    // }


    // for (int i = 0; i < n; i ++) {
    //     if (is_exit[i]) {
    //         cout << "*";
    //     }
    //     cout << "i=" << i << ": ";
    //     cout << dis[i].first << " " << dis[i].second << endl;
    // }

    return 0;
}

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