#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
typedef pair < long long, long long > pll;
const int N = 1e5 + 7, inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int X[] = {1, -1, 0, 0};
const int Y[] = {0, 0, 1, -1};
int n, m, d[N], k, ans, us[N], s, t;
vector < pii > g[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
d[i] = inf;
}
for (int i = 1, u, v, x; i <= m; i++) {
cin >> u >> v >> x;
g[u].push_back(make_pair(v, x));
g[v].push_back(make_pair(u, x));
}
set < pair <int, int> > st;
cin >> k;
for (int i = 1, x; i <= k; i++) {
cin >> x;
d[x] = 0;
st.insert(make_pair(0, x));
}
while(!st.empty()) {
int x = st.begin() -> second;
st.erase(st.begin());
for (int i = 0; i < g[x].size(); ++i) {
int to = g[x][i].first, len = g[x][i].second;
if (d[x] + len < d[to]) {
st.erase(make_pair(d[to], to));
d[to] = d[x] + len;
st.insert(make_pair(d[to], to));
}
}
}
int q;
cin >> q;
while(q--) {
cin >> s >> t;
cout << min(d[s], d[t]) << '\n';
}
return 0;
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:41:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[x].size(); ++i) {
~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2684 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
5 ms |
2680 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2680 KB |
Output is correct |
12 |
Correct |
5 ms |
2780 KB |
Output is correct |
13 |
Correct |
5 ms |
2680 KB |
Output is correct |
14 |
Correct |
4 ms |
2680 KB |
Output is correct |
15 |
Correct |
5 ms |
2680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2684 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
5 ms |
2680 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2680 KB |
Output is correct |
12 |
Correct |
5 ms |
2780 KB |
Output is correct |
13 |
Correct |
5 ms |
2680 KB |
Output is correct |
14 |
Correct |
4 ms |
2680 KB |
Output is correct |
15 |
Correct |
5 ms |
2680 KB |
Output is correct |
16 |
Correct |
141 ms |
8204 KB |
Output is correct |
17 |
Correct |
554 ms |
20476 KB |
Output is correct |
18 |
Correct |
36 ms |
4344 KB |
Output is correct |
19 |
Correct |
144 ms |
12396 KB |
Output is correct |
20 |
Correct |
559 ms |
20384 KB |
Output is correct |
21 |
Correct |
254 ms |
13020 KB |
Output is correct |
22 |
Correct |
106 ms |
7580 KB |
Output is correct |
23 |
Correct |
563 ms |
20496 KB |
Output is correct |
24 |
Correct |
563 ms |
20512 KB |
Output is correct |
25 |
Correct |
586 ms |
20468 KB |
Output is correct |
26 |
Correct |
142 ms |
12264 KB |
Output is correct |
27 |
Correct |
138 ms |
12492 KB |
Output is correct |
28 |
Correct |
140 ms |
12276 KB |
Output is correct |
29 |
Correct |
141 ms |
12468 KB |
Output is correct |
30 |
Correct |
142 ms |
12336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
2652 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
231 ms |
11408 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2684 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
5 ms |
2680 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2680 KB |
Output is correct |
12 |
Correct |
5 ms |
2780 KB |
Output is correct |
13 |
Correct |
5 ms |
2680 KB |
Output is correct |
14 |
Correct |
4 ms |
2680 KB |
Output is correct |
15 |
Correct |
5 ms |
2680 KB |
Output is correct |
16 |
Correct |
141 ms |
8204 KB |
Output is correct |
17 |
Correct |
554 ms |
20476 KB |
Output is correct |
18 |
Correct |
36 ms |
4344 KB |
Output is correct |
19 |
Correct |
144 ms |
12396 KB |
Output is correct |
20 |
Correct |
559 ms |
20384 KB |
Output is correct |
21 |
Correct |
254 ms |
13020 KB |
Output is correct |
22 |
Correct |
106 ms |
7580 KB |
Output is correct |
23 |
Correct |
563 ms |
20496 KB |
Output is correct |
24 |
Correct |
563 ms |
20512 KB |
Output is correct |
25 |
Correct |
586 ms |
20468 KB |
Output is correct |
26 |
Correct |
142 ms |
12264 KB |
Output is correct |
27 |
Correct |
138 ms |
12492 KB |
Output is correct |
28 |
Correct |
140 ms |
12276 KB |
Output is correct |
29 |
Correct |
141 ms |
12468 KB |
Output is correct |
30 |
Correct |
142 ms |
12336 KB |
Output is correct |
31 |
Incorrect |
4 ms |
2652 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |