Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF=1e9;
- using pi=pair<int,int>;
- int n,m,p;
- vector <pi> g[40001];
- pi connect[50001];
- int color[40001];
- void dfs(int u,int c,int d){
- if(color[u]!=0) return ;
- color[u]=c;
- for(auto vw:g[u]){
- int v,w;
- v=vw.first;
- w=vw.second;
- if(color[v]==0 and w<d) dfs(v,c,d);
- }
- }
- int main(){
- int l=INF,r=-INF,mid;
- scanf("%d %d %d",&n,&m,&p);
- for(int i=1;i<=m;i++){
- int u,v,w;
- scanf("%d %d %d",&u,&v,&w);
- g[u].push_back({v,w});
- g[v].push_back({u,w});
- l=min(l,w);
- r=max(r,w);
- }
- int c=1;
- for(int i=1;i<=n;i++){
- if(color[i]==0){
- dfs(i,c,INF);
- c++;
- }
- }
- int check=0;
- for(int i=1;i<=p;i++){
- int u,v;
- scanf("%d%d",&u,&v);
- connect[i]={u,v};
- if(color[u]!=color[v]) check++;
- }
- if(check==p){
- printf("-1");
- return 0;
- }
- int max_k=0;
- while(l<=r){
- mid=(l+r)/2;
- c=1;
- for(int i=1;i<=n;i++) color[i]=0;
- for(int i=1;i<=n;i++){
- if(color[i]==0){
- dfs(i,c,mid);
- c++;
- }
- }
- int cannot_connect=0;
- for(int i=1;i<=p;i++){
- int u,v;
- u=connect[i].first;
- v=connect[i].second;
- if(color[u]!=color[v]) cannot_connect++;
- }
- if(cannot_connect>=p){
- max_k=max(max_k,mid);
- l=mid+1;
- }
- else r=mid-1;
- }
- printf("%d",max_k);
- return 0;
- }
Add Comment
Please, Sign In to add comment