oj.uz

답안 #51741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51741 2018-06-20T19:51:30 Z hugo_pm Evacuation plan (IZhO18_plan) C++14
23 / 100
 1232 ms 26360 KB 
#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);

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()
{
    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();
    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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 6 ms 3192 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 5 ms 3112 KB Output is correct
6 Correct 6 ms 3192 KB Output is correct
7 Correct 4 ms 3036 KB Output is correct
8 Correct 5 ms 3036 KB Output is correct
9 Correct 5 ms 3192 KB Output is correct
10 Correct 5 ms 3064 KB Output is correct
11 Correct 5 ms 3068 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct
13 Correct 6 ms 3064 KB Output is correct
14 Correct 0 ms 3064 KB Output is correct
15 Correct 6 ms 3064 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 6 ms 3192 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 5 ms 3112 KB Output is correct
6 Correct 6 ms 3192 KB Output is correct
7 Correct 4 ms 3036 KB Output is correct
8 Correct 5 ms 3036 KB Output is correct
9 Correct 5 ms 3192 KB Output is correct
10 Correct 5 ms 3064 KB Output is correct
11 Correct 5 ms 3068 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct
13 Correct 6 ms 3064 KB Output is correct
14 Correct 0 ms 3064 KB Output is correct
15 Correct 6 ms 3064 KB Output is correct
16 Correct 228 ms 8272 KB Output is correct
17 Correct 1232 ms 26284 KB Output is correct
18 Correct 80 ms 5008 KB Output is correct
19 Correct 198 ms 9656 KB Output is correct
20 Correct 1182 ms 26300 KB Output is correct
21 Correct 245 ms 11516 KB Output is correct
22 Correct 124 ms 7900 KB Output is correct
23 Correct 1014 ms 26360 KB Output is correct
24 Correct 1004 ms 22632 KB Output is correct
25 Correct 606 ms 20596 KB Output is correct
26 Correct 117 ms 9044 KB Output is correct
27 Correct 117 ms 9036 KB Output is correct
28 Correct 143 ms 9592 KB Output is correct
29 Correct 142 ms 9904 KB Output is correct
30 Correct 121 ms 9088 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 459 ms 15020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3064 KB Output is correct
3 Correct 6 ms 3192 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 5 ms 3112 KB Output is correct
6 Correct 6 ms 3192 KB Output is correct
7 Correct 4 ms 3036 KB Output is correct
8 Correct 5 ms 3036 KB Output is correct
9 Correct 5 ms 3192 KB Output is correct
10 Correct 5 ms 3064 KB Output is correct
11 Correct 5 ms 3068 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct
13 Correct 6 ms 3064 KB Output is correct
14 Correct 0 ms 3064 KB Output is correct
15 Correct 6 ms 3064 KB Output is correct
16 Correct 228 ms 8272 KB Output is correct
17 Correct 1232 ms 26284 KB Output is correct
18 Correct 80 ms 5008 KB Output is correct
19 Correct 198 ms 9656 KB Output is correct
20 Correct 1182 ms 26300 KB Output is correct
21 Correct 245 ms 11516 KB Output is correct
22 Correct 124 ms 7900 KB Output is correct
23 Correct 1014 ms 26360 KB Output is correct
24 Correct 1004 ms 22632 KB Output is correct
25 Correct 606 ms 20596 KB Output is correct
26 Correct 117 ms 9044 KB Output is correct
27 Correct 117 ms 9036 KB Output is correct
28 Correct 143 ms 9592 KB Output is correct
29 Correct 142 ms 9904 KB Output is correct
30 Correct 121 ms 9088 KB Output is correct
31 Incorrect 4 ms 3148 KB Output isn't correct
32 Halted 0 ms 0 KB -