#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
ll n, m, k, a, b;
ll dista[maxn], distb[maxn];
vector<int>g[maxn];
set<int>edge[maxn];
vector<int>unsolved[maxn];
bool visiteda[maxn], visitedb[maxn];
void bfs() {
for(int i=1;i<=n;i++) dista[i] = 1e9;
queue<int>q;
visiteda[k] = true;
dista[k] = 0;
q.push(k);
while(!q.empty()) {
int curr = q.front();
q.pop();
for(int i:g[curr]) {
if(!visiteda[i]) {
visiteda[i] = true;
dista[i] = dista[curr] + 1;
q.push(i);
}
}
}
}
void bfsb() {
for(int i=1;i<=n;i++) distb[i] = 1e9;
queue<int>q;
visitedb[k] = true;
distb[k] = 0;
q.push(k);
while(!q.empty()) {
int curr = q.front(); q.pop();
for(int i:g[curr]) {
vector<int>temp;
for(int j:unsolved[i]) {
if(visitedb[j]) continue;
temp.pb(j);
if(edge[j].find(curr) != edge[j].end()) {
continue;
}
visitedb[j] = true;
distb[j] = distb[curr] + 1;
q.push(j);
}
unsolved[i] = temp;
}
}
}
int main() {
cin>>n>>m>>k>>a>>b;
int x, y;
for(int i=0;i<m;i++) {
cin>>x>>y;
g[x].pb(y); g[y].pb(x);
edge[x].insert(y); edge[y].insert(x);
unsolved[x].pb(y); unsolved[y].pb(x);
}
bfs();
bfsb();
for(int i=1;i<=n;i++) {
if(dista[i] % 2 == 0) {
cout<<min(dista[i]*a, (dista[i]/2)*b)<<"\n";
}
else {
ll cb = INT_MAX;
if(visitedb[i]) cb = distb[i] * b;
cout<<min(((dista[i]-1)/2*b)+a,cb)<<"\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
11 ms |
9728 KB |
Output is correct |
3 |
Correct |
11 ms |
9856 KB |
Output is correct |
4 |
Correct |
11 ms |
9856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
9856 KB |
Output is correct |
2 |
Correct |
12 ms |
9856 KB |
Output is correct |
3 |
Correct |
12 ms |
9856 KB |
Output is correct |
4 |
Correct |
14 ms |
9984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
12000 KB |
Output is correct |
2 |
Correct |
34 ms |
11904 KB |
Output is correct |
3 |
Correct |
53 ms |
12408 KB |
Output is correct |
4 |
Correct |
57 ms |
12536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
17180 KB |
Output is correct |
2 |
Correct |
125 ms |
17284 KB |
Output is correct |
3 |
Correct |
136 ms |
16152 KB |
Output is correct |
4 |
Correct |
232 ms |
18624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
246 ms |
22880 KB |
Output is correct |
2 |
Correct |
243 ms |
21296 KB |
Output is correct |
3 |
Correct |
417 ms |
24568 KB |
Output is correct |
4 |
Correct |
382 ms |
25164 KB |
Output is correct |
5 |
Correct |
253 ms |
23908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
264 ms |
25368 KB |
Output is correct |
2 |
Correct |
222 ms |
21816 KB |
Output is correct |
3 |
Correct |
386 ms |
25624 KB |
Output is correct |
4 |
Correct |
366 ms |
25228 KB |
Output is correct |
5 |
Correct |
303 ms |
25556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
360 ms |
28136 KB |
Output is correct |
2 |
Correct |
334 ms |
26340 KB |
Output is correct |
3 |
Correct |
386 ms |
26260 KB |
Output is correct |
4 |
Correct |
354 ms |
24952 KB |
Output is correct |
5 |
Correct |
303 ms |
27164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
384 ms |
27160 KB |
Output is correct |
2 |
Correct |
408 ms |
26996 KB |
Output is correct |
3 |
Correct |
411 ms |
26588 KB |
Output is correct |
4 |
Correct |
363 ms |
25192 KB |
Output is correct |
5 |
Correct |
291 ms |
28292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
311 ms |
27808 KB |
Output is correct |
2 |
Correct |
302 ms |
27640 KB |
Output is correct |
3 |
Correct |
392 ms |
27832 KB |
Output is correct |
4 |
Correct |
349 ms |
25080 KB |
Output is correct |
5 |
Correct |
366 ms |
28472 KB |
Output is correct |