제출 #1268446

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

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int n, int m, int kr[][2], int dl[], int k, int wyjscia[]){
//cout << "lets do this" << endl;
//cout << n << ' ' << m << ' ' << k << endl;
    vector<pair<int, long long>> graf[n + 1];
    for(int i = 0; i < m; i++){
        graf[kr[i][0]].push_back({kr[i][1], dl[i]});
        graf[kr[i][1]].push_back({kr[i][0], dl[i]});
    }

    priority_queue<pair<long long, int>> Q;
    int sumy[n];
    bool odw[n];
    long long wyn[n];
    long long minn[n];
    for(int i = 0; i < n; i++){
        sumy[i] = 0;
        wyn[i] = LLONG_MAX;
        odw[i] = 0;
    }
    for(int i = 0; i < k; i++){
        Q.push({0, wyjscia[i]});
        sumy[wyjscia[i]] = 2;
        wyn[wyjscia[i]] = 0;
    }

    //cout << "cos nie pyklo" << endl;

    while(!(Q.empty())){
        int v = Q.top().second;
        long long odl = -Q.top().first;
        Q.pop();

        if(odw[v]){continue;}
        odw[v] = 1;

 //       cout << "Jestem w " << v << " z wynikiem " << wyn[v] << endl;

        for(auto i:graf[v]){
            if(odw[i.first]){continue;}
            if(!sumy[i.first]){
                minn[i.first] = wyn[v] + i.second;
            }
            else{
                if(wyn[v] + i.second <= minn[i.first]){
                    wyn[i.first] = minn[i.first];
                    minn[i.first] = wyn[v] + i.second;
                    Q.push({-wyn[i.first], i.first});
                }
                else if(wyn[v] + i.second < wyn[i.first]){
                    wyn[i.first] = wyn[v] + i.second;
                    Q.push({-wyn[i.first], i.first});
                }
            }
            sumy[i.first]++;
        }
    }
    return wyn[0];
}

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