제출 #378560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378560		joylintp	Evacuation plan (IZhO18_plan)	C++17	23 / 100	404 ms	20584 KiB

plan

#include<bits/stdc++.h>
using namespace std;

//#pragma gcc optimize("Ofast,unroll-loops")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double
#define MP make_pair
#define F first
#define S second
#define MOD 1000000007

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    int a, b, w;
    vector<vector<pair<int, int>>> edge(N + 1);
    while (M--)
        cin >> a >> b >> w, edge[a].push_back(MP(b, w)), edge[b].push_back(MP(a, w));

    int k, g;
    vector<int> dis(N + 1, 2e9);
    priority_queue<pair<int, int>> pq;
    cin >> k;
    while (k--)
        cin >> g, dis[g] = 0, pq.push(MP(0, g));

    vector<bool> vis(N + 1);
    while (!pq.empty())
    {
        int d = -pq.top().F, u = pq.top().S;
        pq.pop();

        if (vis[u])
            continue;

        vis[u] = true;
        for (auto p : edge[u])
            if (!vis[p.F] && dis[p.F] > d + p.S)
                dis[p.F] = d + p.S, pq.push(MP(-dis[p.F], p.F));
    }

    int Q, s, t;
    cin >> Q;
    while (Q--)
    {
        cin >> s >> t;
        cout << min(dis[s], dis[t]) << '\n';
    }

    return 0;
}

//      *   *  *****  *   *  *   *   ****  ****    ****     **    **
//     *   *  *      **  *  *   *  *      *   *  *        * *   * *
//    *****  *****  * * *  *   *  *      ****   *       *  *     *
//   *   *      *  *  **  *   *  *      *  *   *       *****    *
//  *   *  *****  *   *   ***    ****  *   *    ****     *   *****

//      *****  *****  *   *  *      *****  *   *  *****  *****
//        *   *   *  *   *  *        *    **  *    *    *   *
//       *   *   *  *****  *        *    * * *    *    *****
//   *  *   *   *    *    *        *    *  **    *    *
//  ****   *****    *    *****  *****  *   *    *    *

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