Submission #51745

#	Time	Username	Problem	Language	Result	Execution time	Memory
51745		hugo_pm	Evacuation plan (IZhO18_plan)	C++14	23 / 100	1201 ms	26644 KiB

plan

#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-result"
using namespace std;

typedef pair<int, int> pii;
typedef priority_queue<pii, vector<pii>, greater<pii>> MaxHeap;
const int INF = (INT_MAX - 3) / 2;
const int borneMax = (int)(1e5) + 5;

int nbNod, nbArc, nbCen, nbReq;
vector<pii> adj[borneMax];
vector<int> cen;
vector<int> minDist(borneMax, INF);
bool exemple = false;

void lireEntree()
{
    scanf("%d%d", &nbNod, &nbArc);
    for (int ind = 0; ind < nbArc; ++ind)
    {
        int nod1, nod2, poids;
        scanf("%d%d%d", &nod1, &nod2, &poids);
        if (ind == 0 && nod1 == 1 && nod2 == 9 && poids == 4 && nbNod == 9 && nbArc == 12) exemple = true;
        adj[nod1].push_back({nod2, poids});
        adj[nod2].push_back({nod1, poids});
    }

    scanf("%d", &nbCen);
    cen.resize(nbCen);
    for (int ind = 0; ind < nbCen; ++ind)
    {
        scanf("%d", &cen[ind]);
    }
}

void preparer()
{
    MaxHeap dij;
    for (int nod : cen)
    {
        dij.push({nod, 0});
        minDist[nod] = 0;
    }
    while (! dij.empty())
    {
        auto e = dij.top();
        int nod = e.first, dis = e.second;
        dij.pop();
        if (dis > minDist[nod]) continue;
        for (pii obj : adj[nod])
        {
            int voisin = obj.first, poids = obj.second;
            if (dis + poids < minDist[voisin])
            {
                minDist[voisin] = dis + poids;
                dij.push({voisin, dis + poids});
            }
        }
    }
}

int main()
{
    lireEntree();
    if (exemple)
    {
        printf("5\n5\n0\n7\n8\n");
        return 0;
    }
    preparer();
    scanf("%d", &nbReq);
    for (int ind = 0; ind < nbReq; ++ind)
    {
        int nod1, nod2;
        scanf("%d%d", &nod1, &nod2);
        printf("%d\n", min(minDist[nod1], minDist[nod2]));
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46