#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;
if(edge[j].find(curr) != edge[j].end()) {
temp.pb(j);
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 |
12 ms |
9720 KB |
Output is correct |
2 |
Incorrect |
11 ms |
9728 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
9728 KB |
Output is correct |
2 |
Correct |
11 ms |
9756 KB |
Output is correct |
3 |
Correct |
12 ms |
9728 KB |
Output is correct |
4 |
Correct |
11 ms |
9728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
9856 KB |
Output is correct |
2 |
Correct |
13 ms |
9856 KB |
Output is correct |
3 |
Correct |
16 ms |
9856 KB |
Output is correct |
4 |
Correct |
14 ms |
9984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
12024 KB |
Output is correct |
2 |
Correct |
32 ms |
12096 KB |
Output is correct |
3 |
Correct |
52 ms |
12668 KB |
Output is correct |
4 |
Correct |
49 ms |
12792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
17656 KB |
Output is correct |
2 |
Correct |
127 ms |
17700 KB |
Output is correct |
3 |
Correct |
142 ms |
16604 KB |
Output is correct |
4 |
Correct |
187 ms |
19292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
207 ms |
23544 KB |
Output is correct |
2 |
Correct |
207 ms |
21880 KB |
Output is correct |
3 |
Correct |
310 ms |
25532 KB |
Output is correct |
4 |
Correct |
348 ms |
26268 KB |
Output is correct |
5 |
Correct |
221 ms |
24508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
239 ms |
26316 KB |
Output is correct |
2 |
Correct |
221 ms |
22392 KB |
Output is correct |
3 |
Correct |
332 ms |
26744 KB |
Output is correct |
4 |
Correct |
347 ms |
26292 KB |
Output is correct |
5 |
Correct |
237 ms |
26428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
29412 KB |
Output is correct |
2 |
Correct |
323 ms |
27292 KB |
Output is correct |
3 |
Correct |
379 ms |
27688 KB |
Output is correct |
4 |
Correct |
420 ms |
26232 KB |
Output is correct |
5 |
Correct |
284 ms |
28260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
27968 KB |
Output is correct |
2 |
Correct |
344 ms |
28128 KB |
Output is correct |
3 |
Correct |
346 ms |
27896 KB |
Output is correct |
4 |
Correct |
386 ms |
26480 KB |
Output is correct |
5 |
Correct |
314 ms |
29492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
29076 KB |
Output is correct |
2 |
Correct |
351 ms |
28860 KB |
Output is correct |
3 |
Correct |
429 ms |
29096 KB |
Output is correct |
4 |
Correct |
423 ms |
26360 KB |
Output is correct |
5 |
Correct |
394 ms |
29480 KB |
Output is correct |