Submission #571449

#	Time	Username	Problem	Language	Result	Execution time	Memory
571449		Doanxem99	Evacuation plan (IZhO18_plan)	C++14	10 / 100	4064 ms	19276 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define ar array< int , 2>
#define arr array< int , 3>
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
const int MAX = 1e5 + 1000;
int d[MAX], dd[MAX], n, m, x, y, z, npp[MAX], k, q;
bool NPP[MAX];
vector < ar > A[MAX];
void DFS(int x)
{
    for (ar y : A[x])
    {
        if (!NPP[y[0]] && d[y[0]] > d[x] + y[1])
        {
            d[y[0]] = d[x] + y[1];
            //dd[x][y[0]] = d[y[0]];
            //dd[y[0]][x] = d[y[0]];
            DFS(y[0]);
        }
    }
}
int BFS(int s, int t)
{
    priority_queue< ar > QU;
    QU.push({d[s], s});
    while (!QU.empty())
    {
        ar x = QU.top();
        QU.pop();
        if (x[1] == t) return x[0];
        for (ar y : A[x[1]])
        {
            if (dd[y[0]] < min(d[y[0]], x[0]))
            {
                dd[y[0]] = min(d[y[0]], x[0]);
                QU.push({dd[y[0]], y[0]});
            }
        }
    }
}
void BFS2()
{
    queue< ar > QU;
    for (int i = 1; i <= k; i++)
    {
        QU.push({0, npp[i]});
    }
    while (!QU.empty())
    {
        ar x = QU.front();
        QU.pop();
        for (ar y : A[x[1]])
        {
            if (d[y[0]] > d[x[1]] + y[1])
            {
                d[y[0]] = d[x[1]] + y[1];
                QU.push({d[y[0]], 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 (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        A[x].push_back({y, z});
        A[y].push_back({x, z});
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> npp[i];
        NPP[npp[i]] = 1;
        d[npp[i]] = 0;
    }
    BFS2();
    //for (int i = 1; i <= n; i++) cout << d[i] << " " ;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> x >> y;
        memset(dd, 0, sizeof dd);
        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
*/

Compilation message (stderr)

plan.cpp: In function 'int BFS(int, int)':
plan.cpp:26:26: warning: control reaches end of non-void function [-Wreturn-type]
   26 |     priority_queue< ar > QU;
      |                          ^~

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