Submission #426166

#	Time	Username	Problem	Language	Result	Execution time	Memory
426166		JeanBombeur	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	940 ms	86604 KiB

crocodile

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include "crocodile.h"
using namespace std;

const long long INFINI = (1000 * 1000 * 1000);
const int MAX_NOEUDS = (100 * 1000);

vector <pair <int, long long>> Voisins[MAX_NOEUDS];

pair <long long, long long> DistMin[MAX_NOEUDS];

bool Vu[MAX_NOEUDS];

priority_queue <pair <long long, int>> Dijkstra;

void Push() {
    int noeud = Dijkstra.top().second;
    long long dist = DistMin[noeud].second;
    Dijkstra.pop();
    if (Vu[noeud])
        return;
    Vu[noeud] = true;
    for (pair <int, long long> dest : Voisins[noeud])
    {
        if (!Vu[dest.first])
        {
            long long nouvDist = dist + dest.second;
            if (nouvDist <= DistMin[dest.first].first)
            {
                DistMin[dest.first].second = DistMin[dest.first].first;
                DistMin[dest.first].first = nouvDist;
            }
            else if (nouvDist < DistMin[dest.first].second)
                DistMin[dest.first].second = nouvDist;
            if (DistMin[dest.first].second < INFINI)
                Dijkstra.push({- DistMin[dest.first].second, dest.first});
        }
    }
    return;
}

int travel_plan(int nbNoeuds, int nbAretes, int Aretes[][2], int Longueur[], int nbSorties, int Sorties[]) {
    
    for (int i = 0; i < nbNoeuds; i ++)
    {
        DistMin[i].first = DistMin[i].second = INFINI;
    }
    
    for (int i = 0; i < nbAretes; i ++)
    {
        Voisins[Aretes[i][0]].push_back({Aretes[i][1], (long long)Longueur[i]});
        Voisins[Aretes[i][1]].push_back({Aretes[i][0], (long long)Longueur[i]});
    }
    
    for (int i = 0; i < nbSorties; i ++)
    {
        DistMin[Sorties[i]].first = DistMin[Sorties[i]].second = 0LL;
        Dijkstra.push({0LL, Sorties[i]});
    }
    
    while (!Dijkstra.empty())
    {
        Push();
    }
    
    return (int)DistMin[0].second;
}

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