-
Notifications
You must be signed in to change notification settings - Fork 15
/
Solution02.cpp
62 lines (55 loc) · 1.32 KB
/
Solution02.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
#includes<iostream>
using namespace std;
#define ll long long int
vector<int> xx[1001];
vector<pair<ll,vector<ll>>> px;
void dfs(ll st,ll e,ll vis[],vector<ll> rs,ll w);
int main() {
ll n,m,t,c,u,v;
cin>>n>>m>>t>>c;
while(m--) {
cin>>u>>v;
xx[u].push_back(v);
xx[v].push_back(u);
}
vector<ll> rs;
ll w = c;
ll vis[n+1] = {0};
dfs(1,n,vis,rs,w);
sort(px.begin(),px.end());
vector<ll> first_arr[n+1];
for(int i=0;i<px.size();i++){
ll nes = px[i].second.size();
for(auto u : px[i].second){
first_arr[u].push_back(nes);
}
}
ll second_arr[n+1] = {0};
second_arr[1] = 1;
second_arr[n] = 1;
for(int i=2;i<=n-1;i++) {
if(first_arr[i].size() > 0) {
ll tm = first_arr[i][0];
ll up = upper_bound(first_arr[i].begin(),first_arr[i].end(),tm) - first_arr[i].begin();
second_arr[i] = up;
}
}
for(int i=1;i<=n;i++)
cout<<second_arr[i]<<" ";
return 0;
}
void dfs(ll st,ll e,ll vis[],vector<ll> rs,ll w) {
rs.push_back(st);
if(st == e) {
px.push_back({w*(rs.size()-1),rs});
return;
}
for(auto u : xx[st]) {
if(vis[u] == 0) {
vis[st] = 1;
dfs(u,e,vis,rs,w);
vis[st] = 0;
}
}
}