제출 #51746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51746		hugo_pm	Evacuation plan (IZhO18_plan)	C++14	54 / 100	4075 ms	37200 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>> MinHeap;
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> valeur(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);
        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()
{
    MinHeap dij;
    for (int nod : cen)
    {
        dij.push({nod, 0});
        valeur[nod] = 0;
    }
    while (! dij.empty())
    {
        auto e = dij.top();
        int nod = e.first, dis = e.second;
        dij.pop();
        if (dis > valeur[nod]) continue;
        for (pii obj : adj[nod])
        {
            int voisin = obj.first, poids = obj.second;
            if (dis + poids < valeur[voisin])
            {
                valeur[voisin] = dis + poids;
                dij.push({voisin, dis + poids});
            }
        }
    }
}

int solve(int nod1, int nod2)
{
    for (auto obj : adj[nod1])
    {
        if (obj.first == nod2)
            return min(valeur[nod1], valeur[nod2]);
    }

    priority_queue<pii> dij;
    vector<int> meilleur(borneMax, 0);
    dij.push({nod1, valeur[nod1]});
    meilleur[nod1] = valeur[nod1];
    while (! dij.empty())
    {
        auto e = dij.top();
        int nod = e.first, dis = e.second;
        dij.pop();
        if (dis < meilleur[nod]) continue;
        for (pii obj : adj[nod])
        {
            int voisin = obj.first;
            int nv = min(dis, valeur[voisin]);
            if (nv > meilleur[voisin])
            {
                meilleur[voisin] = nv;
                dij.push({voisin, nv});
            }
        }
    }
    return meilleur[nod2];
}

int main()
{
    lireEntree();
    preparer();
    scanf("%d", &nbReq);
    for (int ind = 0; ind < nbReq; ++ind)
    {
        int nod1, nod2;
        scanf("%d%d", &nod1, &nod2);
        printf("%d\n", solve(nod1, nod2));
    }
}

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