#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]));
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3040 KB |
Output is correct |
2 |
Correct |
5 ms |
3068 KB |
Output is correct |
3 |
Correct |
5 ms |
3064 KB |
Output is correct |
4 |
Correct |
4 ms |
3064 KB |
Output is correct |
5 |
Correct |
5 ms |
3068 KB |
Output is correct |
6 |
Correct |
6 ms |
3064 KB |
Output is correct |
7 |
Correct |
4 ms |
3064 KB |
Output is correct |
8 |
Correct |
4 ms |
3064 KB |
Output is correct |
9 |
Correct |
6 ms |
3192 KB |
Output is correct |
10 |
Correct |
5 ms |
3064 KB |
Output is correct |
11 |
Correct |
6 ms |
3192 KB |
Output is correct |
12 |
Correct |
5 ms |
3064 KB |
Output is correct |
13 |
Correct |
5 ms |
3196 KB |
Output is correct |
14 |
Correct |
5 ms |
3068 KB |
Output is correct |
15 |
Correct |
6 ms |
3064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3040 KB |
Output is correct |
2 |
Correct |
5 ms |
3068 KB |
Output is correct |
3 |
Correct |
5 ms |
3064 KB |
Output is correct |
4 |
Correct |
4 ms |
3064 KB |
Output is correct |
5 |
Correct |
5 ms |
3068 KB |
Output is correct |
6 |
Correct |
6 ms |
3064 KB |
Output is correct |
7 |
Correct |
4 ms |
3064 KB |
Output is correct |
8 |
Correct |
4 ms |
3064 KB |
Output is correct |
9 |
Correct |
6 ms |
3192 KB |
Output is correct |
10 |
Correct |
5 ms |
3064 KB |
Output is correct |
11 |
Correct |
6 ms |
3192 KB |
Output is correct |
12 |
Correct |
5 ms |
3064 KB |
Output is correct |
13 |
Correct |
5 ms |
3196 KB |
Output is correct |
14 |
Correct |
5 ms |
3068 KB |
Output is correct |
15 |
Correct |
6 ms |
3064 KB |
Output is correct |
16 |
Correct |
211 ms |
8784 KB |
Output is correct |
17 |
Correct |
1213 ms |
27076 KB |
Output is correct |
18 |
Correct |
65 ms |
5236 KB |
Output is correct |
19 |
Correct |
198 ms |
10352 KB |
Output is correct |
20 |
Correct |
1140 ms |
27000 KB |
Output is correct |
21 |
Correct |
241 ms |
12096 KB |
Output is correct |
22 |
Correct |
119 ms |
8328 KB |
Output is correct |
23 |
Correct |
1010 ms |
27260 KB |
Output is correct |
24 |
Correct |
899 ms |
23640 KB |
Output is correct |
25 |
Correct |
611 ms |
21952 KB |
Output is correct |
26 |
Correct |
119 ms |
9680 KB |
Output is correct |
27 |
Correct |
123 ms |
9412 KB |
Output is correct |
28 |
Correct |
142 ms |
9804 KB |
Output is correct |
29 |
Correct |
142 ms |
9892 KB |
Output is correct |
30 |
Correct |
117 ms |
9260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
3116 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
475 ms |
15144 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3040 KB |
Output is correct |
2 |
Correct |
5 ms |
3068 KB |
Output is correct |
3 |
Correct |
5 ms |
3064 KB |
Output is correct |
4 |
Correct |
4 ms |
3064 KB |
Output is correct |
5 |
Correct |
5 ms |
3068 KB |
Output is correct |
6 |
Correct |
6 ms |
3064 KB |
Output is correct |
7 |
Correct |
4 ms |
3064 KB |
Output is correct |
8 |
Correct |
4 ms |
3064 KB |
Output is correct |
9 |
Correct |
6 ms |
3192 KB |
Output is correct |
10 |
Correct |
5 ms |
3064 KB |
Output is correct |
11 |
Correct |
6 ms |
3192 KB |
Output is correct |
12 |
Correct |
5 ms |
3064 KB |
Output is correct |
13 |
Correct |
5 ms |
3196 KB |
Output is correct |
14 |
Correct |
5 ms |
3068 KB |
Output is correct |
15 |
Correct |
6 ms |
3064 KB |
Output is correct |
16 |
Correct |
211 ms |
8784 KB |
Output is correct |
17 |
Correct |
1213 ms |
27076 KB |
Output is correct |
18 |
Correct |
65 ms |
5236 KB |
Output is correct |
19 |
Correct |
198 ms |
10352 KB |
Output is correct |
20 |
Correct |
1140 ms |
27000 KB |
Output is correct |
21 |
Correct |
241 ms |
12096 KB |
Output is correct |
22 |
Correct |
119 ms |
8328 KB |
Output is correct |
23 |
Correct |
1010 ms |
27260 KB |
Output is correct |
24 |
Correct |
899 ms |
23640 KB |
Output is correct |
25 |
Correct |
611 ms |
21952 KB |
Output is correct |
26 |
Correct |
119 ms |
9680 KB |
Output is correct |
27 |
Correct |
123 ms |
9412 KB |
Output is correct |
28 |
Correct |
142 ms |
9804 KB |
Output is correct |
29 |
Correct |
142 ms |
9892 KB |
Output is correct |
30 |
Correct |
117 ms |
9260 KB |
Output is correct |
31 |
Incorrect |
4 ms |
3116 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |