제출 #571469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571469		Doanxem99	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4086 ms	60164 KiB

plan

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

#define ar array< long long , 2>
#define arr array< long long , 3>
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

const long long MAX = 1e6 + 7;
long long d[MAX], n, m, x, y, z, npp[MAX], k, q;
bool NPP[MAX];
vector < ar > A[MAX];
long long BFS(long long s, long long t)
{
    vector < long long > dd;
    dd.resize(n + 100, 0);
    dd[s] = d[s];
    queue< long long > QU;
    QU.push(s);
    while (!QU.empty())
    {
        long long x = QU.front();
        QU.pop();
        //if (x[1] == t) return x[0];
        for (ar y : A[x])
        {
            if (dd[y[0]] < min(d[y[0]], dd[x]))
            {
                dd[y[0]] = min(d[y[0]], dd[x]);
                QU.push(y[0]);
            }
        }
    }
    return dd[t];
}
void BFS2()
{
    queue< long long > QU;
    for (long long i = 1; i <= k; i++)
    {
        QU.push(npp[i]);
    }
    while (!QU.empty())
    {
        long long x = QU.front();
        QU.pop();
        for (ar y : A[x])
        {
            if (d[y[0]] > d[x] + y[1])
            {
                d[y[0]] = d[x] + y[1];
                QU.push(y[0]);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for (long long i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        A[x].push_back({y, z});
        A[y].push_back({x, z});
    }
    cin >> k;
    for (long long i = 1; i <= k; i++)
    {
        cin >> npp[i];
        NPP[npp[i]] = 1;
        d[npp[i]] = 0;
    }
    BFS2();
    //for (long long i = 1; i <= n; i++) cout << d[i] << " " ;
    cin >> q;
    for (long long i = 1; i <= q; i++)
    {
        cin >> x >> y;
        if (NPP[x] || NPP[y]) cout << 0 << '\n' ;
        else
            cout << BFS(x, y) << '\n' ;

    }
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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