#include "crocodile.h";
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k) print the k-th smallest number in os(0-based)
int n, m, k;
vector<pii> g[maxn];
bool mark[maxn];
bool spec[maxn]; // ovde ako udjem zavrsavam i treba da vidim do kojih mogu da dodjem
int br[maxn];
bool visited[maxn];
void dfs1(int v){
visited[v] = 1;
if(mark[v]){
for(auto c : g[v]){
int u = c.fi;
int w = c.se;
if(!visited[u])dfs1(u);
}
return;
}
for(auto c : g[v]){
int u = c.fi;
int w = c.se;
if(!visited[u]){
dfs1(u);
}
if(mark[u] == 1)br[v] += 1;
}
}
bool was[maxn];
void dfs2(int v){
cout << "v: " << v << endl;
was[v] = 1;
if(mark[v] == 1 || spec[v] == 1){
for(auto c : g[v]){
int u = c.fi;
int w = c.se;
if(!was[u])dfs2(u);
}
return;
}
for(auto c : g[v]){
int u = c.fi;
int w = c.se;
if(!was[u]){
dfs2(u);
}
if(spec[u] == 1)br[v] += 1;
}
}
ll dist[maxn];
void dij(int sv){
ff(i,1,n)dist[i] = inf;
priority_queue<pii> pq;
pq.push({dist[sv] = 0, sv});
while(!pq.empty()){
pii v = pq.top();pq.pop();
if(dist[v.se] < -v.fi)continue;
for(auto c : g[v.se]){
int u = c.fi;
int w = c.se;
if(dist[u] > w + -v.fi){
dist[u] = -v.fi + w;
pq.push({-dist[u], u});
}
}
}
}
vector<int> koji;
bool used[maxn];
void dfs3(int v){
used[v] = 1;
if(spec[v]){
koji.pb(v);
return;
}
if(br[v] == 0)return;
for(auto c : g[v]){
int u = c.fi;
int w = c.se;
if(!used[u]){
if(br[v] > 1)dfs3(u);
else{
if(br[v] == 1 && (mark[u] || spec[u]))continue;
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N;
m = M;
k = K;
ff(i,0,m - 1){
int u = R[i][0];
int v = R[i][1];
int w = L[i];
g[u].pb({v, w});
g[v].pb({u, w});
}
ff(i,0,k - 1){
int x = P[i];
mark[x] = 1;
}
// moram da vidim koji cvor ima >= 2 izlaza
// i onda samo uzimam drugi najmanju
dfs1(1);
ff(i,1,n){
if(br[i] >= 2)spec[i] = 1;
}
dfs2(1);
// sad treba videti do kojih specijalnih mogu doci
dfs3(1);
dij(1);
vector<int> svi;
for(auto c : koji){
int mn1 = inf;
int mn2 = inf;
for(auto f : g[c]){
int u = f.fi;
if(mark[u]){
if(dist[u] < mn1){
mn2 = mn1;
mn1 = dist[u];
}
else{
if(dist[u] < mn2)mn2 = dist[u];
}
}
}
if(mn2 != inf)svi.pb(mn2);
else svi.pb(mn1);
}
sort(all(svi));
return svi.back();
}
//bool cmp(int s1, int s2){
// return dist[s1] < dist[s2];
//}
//
//int main()
//{
// ios::sync_with_stdio(false);
// cout.tie(nullptr);
// cin.tie(nullptr);
// cin >> n >> m >> k;
// ff(i,1,k){
// int x;
// cin >> x;
// mark[x] = 1;
// }
// ff(i,1,m){
// int u, v, w;
// cin >> u >> v >> w;
// g[u].pb({v, w});
// g[v].pb({u, w});
// }
// // moram da vidim koji cvor ima >= 2 izlaza
// // i onda samo uzimam drugi najmanju
// dfs1(1);
// ff(i,1,n){
// if(br[i] >= 2)spec[i] = 1;
// }
// dfs2(1);
// // sad treba videti do kojih specijalnih mogu doci
// dfs3(1);
// dij(1);
// vector<int> svi;
// for(auto c : koji){
// int mn1 = inf;
// int mn2 = inf;
// for(auto f : g[c]){
// int u = f.fi;
// if(mark[u]){
// if(dist[u] < mn1){
// mn2 = mn1;
// mn1 = dist[u];
// }
// else{
// if(dist[u] < mn2)mn2 = dist[u];
// }
// }
// }
// if(mn2 != inf)svi.pb(mn2);
// else svi.pb(mn1);
// }
// sort(all(svi));
// cout << svi.back() << endl;
// return 0;
//}
/**
5 4 3
2 4 5
1 2 2
1 3 3
4 3 1
3 5 4
8 7 4
4 5 7 8
1 2 1
2 3 1
3 4 1
3 5 1
1 6 1
6 7 1
6 8 1
5 7 2
2 4
1 3 4
1 4 3
4 3 2
3 2 10
1 2 100
1 5 7
4 5 9
// probati bojenje sahovski ili slicno
**/
Compilation message
crocodile.cpp:1:23: warning: extra tokens at end of #include directive
1 | #include "crocodile.h";
| ^
crocodile.cpp: In function 'void dfs1(int)':
crocodile.cpp:43:17: warning: unused variable 'w' [-Wunused-variable]
43 | int w = c.se;
| ^
crocodile.cpp:50:13: warning: unused variable 'w' [-Wunused-variable]
50 | int w = c.se;
| ^
crocodile.cpp: In function 'void dfs2(int)':
crocodile.cpp:65:17: warning: unused variable 'w' [-Wunused-variable]
65 | int w = c.se;
| ^
crocodile.cpp:72:13: warning: unused variable 'w' [-Wunused-variable]
72 | int w = c.se;
| ^
crocodile.cpp: In function 'void dfs3(int)':
crocodile.cpp:110:13: warning: unused variable 'w' [-Wunused-variable]
110 | int w = c.se;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
