#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];
queue < int > qb;
void dfs (int v, int d){
dis[v] = min(dis[v], d);
for (int i = 0; i < g[v].size(); i++){
if (g[v][i].second + d < dis[g[v][i].first])
dfs(g[v][i].first, d + g[v][i].second);
}
}
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--;
qb.push(a);
}
while(!qb.empty()){
int c = qb.front();
qb.pop();
dfs(c, 0);
}
int q;
cin >> q;
for (int i = 0; i < q; i++){
int a, b;
cin >> a >> b;
a--; b--;
cout << min(dis[a], dis[b]) << endl;
}
}
Compilation message
plan.cpp: In function 'void dfs(long long int, long long int)':
plan.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
plan.cpp: At global scope:
plan.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
9 ms |
3576 KB |
Output is correct |
3 |
Correct |
9 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3448 KB |
Output is correct |
5 |
Correct |
9 ms |
3448 KB |
Output is correct |
6 |
Correct |
10 ms |
3448 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
10 ms |
3576 KB |
Output is correct |
10 |
Correct |
10 ms |
3448 KB |
Output is correct |
11 |
Correct |
9 ms |
3448 KB |
Output is correct |
12 |
Correct |
9 ms |
3448 KB |
Output is correct |
13 |
Correct |
9 ms |
3620 KB |
Output is correct |
14 |
Correct |
9 ms |
3448 KB |
Output is correct |
15 |
Correct |
9 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
9 ms |
3576 KB |
Output is correct |
3 |
Correct |
9 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3448 KB |
Output is correct |
5 |
Correct |
9 ms |
3448 KB |
Output is correct |
6 |
Correct |
10 ms |
3448 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
10 ms |
3576 KB |
Output is correct |
10 |
Correct |
10 ms |
3448 KB |
Output is correct |
11 |
Correct |
9 ms |
3448 KB |
Output is correct |
12 |
Correct |
9 ms |
3448 KB |
Output is correct |
13 |
Correct |
9 ms |
3620 KB |
Output is correct |
14 |
Correct |
9 ms |
3448 KB |
Output is correct |
15 |
Correct |
9 ms |
3448 KB |
Output is correct |
16 |
Execution timed out |
4091 ms |
9780 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
3448 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4065 ms |
16436 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
9 ms |
3576 KB |
Output is correct |
3 |
Correct |
9 ms |
3448 KB |
Output is correct |
4 |
Correct |
4 ms |
3448 KB |
Output is correct |
5 |
Correct |
9 ms |
3448 KB |
Output is correct |
6 |
Correct |
10 ms |
3448 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
10 ms |
3576 KB |
Output is correct |
10 |
Correct |
10 ms |
3448 KB |
Output is correct |
11 |
Correct |
9 ms |
3448 KB |
Output is correct |
12 |
Correct |
9 ms |
3448 KB |
Output is correct |
13 |
Correct |
9 ms |
3620 KB |
Output is correct |
14 |
Correct |
9 ms |
3448 KB |
Output is correct |
15 |
Correct |
9 ms |
3448 KB |
Output is correct |
16 |
Execution timed out |
4091 ms |
9780 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |