#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif
int n, m, k, a, b;
cin >> n >> m >> k >> a >> b, --k;
vector<vector<int>> adj(n);
for (int u, v; m--;) {
cin >> u >> v, --u, --v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
vector<int> step(n, -1);
step[k] = 0;
queue<int> q;
q.emplace(k);
while (!q.empty()) {
const auto u = q.front();
q.pop();
for (const auto& v : adj[u])
if (step[v] == -1) {
step[v] = step[u] + 1;
q.emplace(v);
}
}
vector<vector<int>> vtx = adj;
vector<bool> neighbor(n);
vector<int> jump(n, -1);
jump[k] = 0;
q.emplace(k);
while (!q.empty()) {
const auto u = q.front();
q.pop();
for (const auto& v : adj[u])
neighbor[v] = true;
for (const auto& via : adj[u])
vtx[via].erase(remove_if(vtx[via].begin(), vtx[via].end(), [&](auto& v) {
if (neighbor[v] || ~jump[v]) return false;
jump[v] = jump[u] + 1;
q.emplace(v);
return true;
}),
vtx[via].end());
for (const auto& v : adj[u])
neighbor[v] = false;
}
for (int i = 0; i < n; ++i)
cout << min({step[i] * a,
(step[i] & 1) * a + (step[i] >> 1) * b,
~jump[i] ? jump[i] * b : INT_MAX})
<< '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
1824 KB |
Output is correct |
2 |
Correct |
7 ms |
1740 KB |
Output is correct |
3 |
Correct |
11 ms |
1740 KB |
Output is correct |
4 |
Correct |
10 ms |
1744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
5400 KB |
Output is correct |
2 |
Correct |
33 ms |
5444 KB |
Output is correct |
3 |
Correct |
27 ms |
3932 KB |
Output is correct |
4 |
Correct |
35 ms |
5192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
9252 KB |
Output is correct |
2 |
Correct |
44 ms |
8108 KB |
Output is correct |
3 |
Correct |
69 ms |
9184 KB |
Output is correct |
4 |
Correct |
71 ms |
8772 KB |
Output is correct |
5 |
Correct |
54 ms |
9792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
11084 KB |
Output is correct |
2 |
Correct |
47 ms |
8396 KB |
Output is correct |
3 |
Correct |
78 ms |
9044 KB |
Output is correct |
4 |
Correct |
69 ms |
8712 KB |
Output is correct |
5 |
Correct |
61 ms |
11200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
12944 KB |
Output is correct |
2 |
Correct |
79 ms |
11720 KB |
Output is correct |
3 |
Correct |
82 ms |
10436 KB |
Output is correct |
4 |
Correct |
69 ms |
8716 KB |
Output is correct |
5 |
Correct |
71 ms |
12224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
75 ms |
12076 KB |
Output is correct |
2 |
Correct |
79 ms |
12192 KB |
Output is correct |
3 |
Correct |
89 ms |
10824 KB |
Output is correct |
4 |
Correct |
68 ms |
8824 KB |
Output is correct |
5 |
Correct |
84 ms |
13160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
12740 KB |
Output is correct |
2 |
Correct |
83 ms |
12620 KB |
Output is correct |
3 |
Correct |
95 ms |
12656 KB |
Output is correct |
4 |
Correct |
67 ms |
8772 KB |
Output is correct |
5 |
Correct |
74 ms |
13120 KB |
Output is correct |