#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;
vector<vector<int>> graph, graph2;
int dist1[MAXN], dist2[MAXN], vis[MAXN];
int 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, (dist2[i] / 2) * b) << "\n";
else
cout << min({dist1[i] * a, dist2[i] * b, (dist1[i] / 2) * b + a}) << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
1884 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
5624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
9680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
11476 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
63 ms |
13464 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
12636 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
49 ms |
13304 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |