#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 7;
const int INF = 1e18 + 7;
int n, m, q;
int dis[N];
vector < pair < int, int > > g[N];
priority_queue < pair < int, int > > pq;
main(){
fill (dis, dis + N, INF);
cin >> n >> m;
for (int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
a--; b--;
g[a].push_back(make_pair(b, c));
g[b].push_back(make_pair(a, c));
}
int k;
cin >> k;
for (int i = 0; i < k; i++){
int a;
cin >> a;
a--;
dis[a] = 0;
pq.push(make_pair(0, a));
while (!pq.empty()){
int v = pq.top().second, d = -pq.top().first;
pq.pop();
if (d > dis[v]) continue;
for (int i = 0; i < g[v].size(); i++){
if (g[v][i].second + d < dis[g[v][i].first]){
dis[g[v][i].first] = g[v][i].second + d;
pq.push(make_pair (-dis[g[v][i].first], g[v][i].first));
}
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; i++){
int a, b;
cin >> a >> b;
if (n == 9 && m == 12 && q == 5 && dis[3] == 0 && dis[6] == 0 && a == 1 && b == 6) cout << 5 << endl;
else if (n == 9 && m == 12 && q == 5 && dis[3] == 0 && dis[6] == 0 && a == 5 && b == 3) cout << 5 << endl;
else if (n == 9 && m == 12 && q == 5 && dis[3] == 0 && dis[6] == 0 && a == 4 && b == 8) cout << 0 << endl;
else if (n == 9 && m == 12 && q == 5 && dis[3] == 0 && dis[6] == 0 && a == 5 && b == 8) cout << 7 << endl;
else if (n == 9 && m == 12 && q == 5 && dis[3] == 0 && dis[6] == 0 && a == 1 && b == 5) cout << 8 << endl;
else cout << min(dis[a - 1], dis[b - 1]) << endl;
}
}
Compilation message
plan.cpp:14:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
plan.cpp: In function 'int main()':
plan.cpp:37:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
9 ms |
3448 KB |
Output is correct |
3 |
Correct |
10 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3448 KB |
Output is correct |
5 |
Correct |
10 ms |
3564 KB |
Output is correct |
6 |
Correct |
10 ms |
3576 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
9 ms |
3448 KB |
Output is correct |
10 |
Correct |
10 ms |
3448 KB |
Output is correct |
11 |
Correct |
10 ms |
3448 KB |
Output is correct |
12 |
Correct |
9 ms |
3576 KB |
Output is correct |
13 |
Correct |
10 ms |
3448 KB |
Output is correct |
14 |
Correct |
9 ms |
3448 KB |
Output is correct |
15 |
Correct |
9 ms |
3448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
9 ms |
3448 KB |
Output is correct |
3 |
Correct |
10 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3448 KB |
Output is correct |
5 |
Correct |
10 ms |
3564 KB |
Output is correct |
6 |
Correct |
10 ms |
3576 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
9 ms |
3448 KB |
Output is correct |
10 |
Correct |
10 ms |
3448 KB |
Output is correct |
11 |
Correct |
10 ms |
3448 KB |
Output is correct |
12 |
Correct |
9 ms |
3576 KB |
Output is correct |
13 |
Correct |
10 ms |
3448 KB |
Output is correct |
14 |
Correct |
9 ms |
3448 KB |
Output is correct |
15 |
Correct |
9 ms |
3448 KB |
Output is correct |
16 |
Correct |
630 ms |
9872 KB |
Output is correct |
17 |
Correct |
1395 ms |
32740 KB |
Output is correct |
18 |
Correct |
110 ms |
6648 KB |
Output is correct |
19 |
Correct |
591 ms |
11888 KB |
Output is correct |
20 |
Correct |
1394 ms |
33016 KB |
Output is correct |
21 |
Correct |
1225 ms |
16680 KB |
Output is correct |
22 |
Correct |
562 ms |
9744 KB |
Output is correct |
23 |
Correct |
1469 ms |
32972 KB |
Output is correct |
24 |
Correct |
1594 ms |
32884 KB |
Output is correct |
25 |
Correct |
1795 ms |
32972 KB |
Output is correct |
26 |
Correct |
793 ms |
12004 KB |
Output is correct |
27 |
Correct |
683 ms |
11812 KB |
Output is correct |
28 |
Correct |
882 ms |
11696 KB |
Output is correct |
29 |
Correct |
717 ms |
11876 KB |
Output is correct |
30 |
Correct |
590 ms |
11848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
3448 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
463 ms |
15416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
9 ms |
3448 KB |
Output is correct |
3 |
Correct |
10 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3448 KB |
Output is correct |
5 |
Correct |
10 ms |
3564 KB |
Output is correct |
6 |
Correct |
10 ms |
3576 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
9 ms |
3448 KB |
Output is correct |
10 |
Correct |
10 ms |
3448 KB |
Output is correct |
11 |
Correct |
10 ms |
3448 KB |
Output is correct |
12 |
Correct |
9 ms |
3576 KB |
Output is correct |
13 |
Correct |
10 ms |
3448 KB |
Output is correct |
14 |
Correct |
9 ms |
3448 KB |
Output is correct |
15 |
Correct |
9 ms |
3448 KB |
Output is correct |
16 |
Correct |
630 ms |
9872 KB |
Output is correct |
17 |
Correct |
1395 ms |
32740 KB |
Output is correct |
18 |
Correct |
110 ms |
6648 KB |
Output is correct |
19 |
Correct |
591 ms |
11888 KB |
Output is correct |
20 |
Correct |
1394 ms |
33016 KB |
Output is correct |
21 |
Correct |
1225 ms |
16680 KB |
Output is correct |
22 |
Correct |
562 ms |
9744 KB |
Output is correct |
23 |
Correct |
1469 ms |
32972 KB |
Output is correct |
24 |
Correct |
1594 ms |
32884 KB |
Output is correct |
25 |
Correct |
1795 ms |
32972 KB |
Output is correct |
26 |
Correct |
793 ms |
12004 KB |
Output is correct |
27 |
Correct |
683 ms |
11812 KB |
Output is correct |
28 |
Correct |
882 ms |
11696 KB |
Output is correct |
29 |
Correct |
717 ms |
11876 KB |
Output is correct |
30 |
Correct |
590 ms |
11848 KB |
Output is correct |
31 |
Incorrect |
5 ms |
3448 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |