#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 998244353;
const ll MAXN = 1e5 + 100;
#define int long long
vector<vector<int>> graph, graph2;
int dist1[MAXN], dist2[MAXN], vis[MAXN];
signed main() {
fast
int n, m, k, a, b;
cin >> n >> m >> k >> a >> b;
graph = vector<vector<int>>(n+1, vector<int>());
for (int i = 0; i < m; i++) {
int q, p;
cin >> q >> p;
graph[q].push_back(p);
graph[p].push_back(q);
}
graph2 = graph;
for (int i = 1; i <= n; i++)
sort(graph[i].begin(), graph[i].end());
queue<pair<int,int>> q;
q.push({0, k});
for (int i = 0; i <= n; i++)
dist1[i] = dist2[i] = 1e9;
dist2[k] = dist1[k] = 0;
while (!q.empty()) {
int node = q.front().s;
q.pop();
if (vis[node])
continue;
vis[node] = true;
for (auto u : graph[node]) {
if (dist1[u] > dist1[node] + 1) {
dist1[u] = dist1[node] + 1;
q.push({dist1[u], u});
}
}
}
for (int i = 0; i <= n; i++)
vis[i] = false;
q.push({0, k});
vis[k] = true;
while (!q.empty()) {
int node = q.front().s;
q.pop();
for (auto node1 : graph[node]) {
for (auto node2 : graph2[node1]) {
if (vis[node2])
continue;
if (*lower_bound(graph[node].begin(), graph[node].end(), node2) == node2)
continue;
dist2[node2] = dist2[node] + 1;
vis[node2] = true;
q.push({dist2[node2], node2});
}
vector<int> v;
for (auto node2 : graph2[node1])
if (!vis[node2])
v.push_back(node2);
swap(graph2[node1], v);
}
}
for (int i = 1; i <= n; i++) {
if (dist1[i] % 2 == 0)
cout << min(dist1[i] * a, (dist1[i] / 2) * b) << "\n";
else
cout << min({dist1[i] * a, dist2[i] * b, (dist1[i] / 2) * b + a}) << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2520 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2592 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4188 KB |
Output is correct |
2 |
Correct |
6 ms |
4188 KB |
Output is correct |
3 |
Correct |
8 ms |
4312 KB |
Output is correct |
4 |
Correct |
8 ms |
4188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8152 KB |
Output is correct |
2 |
Correct |
19 ms |
8248 KB |
Output is correct |
3 |
Incorrect |
23 ms |
6744 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
12080 KB |
Output is correct |
2 |
Correct |
31 ms |
10580 KB |
Output is correct |
3 |
Incorrect |
50 ms |
12388 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
13832 KB |
Output is correct |
2 |
Correct |
36 ms |
10840 KB |
Output is correct |
3 |
Incorrect |
52 ms |
12860 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
15612 KB |
Output is correct |
2 |
Correct |
54 ms |
14340 KB |
Output is correct |
3 |
Incorrect |
70 ms |
13832 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
14676 KB |
Output is correct |
2 |
Correct |
51 ms |
14672 KB |
Output is correct |
3 |
Incorrect |
54 ms |
14148 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
15184 KB |
Output is correct |
2 |
Correct |
49 ms |
15148 KB |
Output is correct |
3 |
Correct |
65 ms |
15700 KB |
Output is correct |
4 |
Correct |
46 ms |
12424 KB |
Output is correct |
5 |
Correct |
54 ms |
16212 KB |
Output is correct |