fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. bool allNodesReachablefromZero(int maxWeightofEdge, vector<vector<int>> &edges,int countNodes)
  6. {
  7. 	vector<vector<int>> adj (countNodes);
  8. 	vector<int> visited (countNodes,0);
  9. 	for(int i=0;i<edges.size();i++)
  10. 	{
  11. 		int x = edges[i][0];
  12. 		int y = edges[i][1];
  13. 		int weight = edges[i][2];
  14. 		if(weight<=maxWeightofEdge)
  15. 		{
  16. 			adj[y].push_back(x);
  17. 		}
  18. 	}
  19. 	queue<int> q;
  20. 	q.push(0);
  21. 	visited[0]=1;
  22. 	while(q.size()>0)
  23. 	{
  24. 		int node = q.front();
  25. 		q.pop();
  26. 		for(int i=0;i<adj[node].size();i++)
  27. 		{
  28. 			if(visited[adj[node][i]]==0)
  29. 			{
  30. 				visited[adj[node][i]] =1;
  31. 				q.push(adj[node][i]);
  32. 			}
  33. 		}
  34.  
  35. 	}
  36. 	for(int i=0;i<countNodes;i++)
  37. 	{
  38. 		if(visited[i]==0)
  39. 		return false;
  40. 	}
  41. 	return true;
  42. }
  43.  
  44. int maxWeight(int n,int threshold,vector<vector<int>> & edges)
  45. {
  46. 	if(n<=1)
  47. 	return 0;
  48. 	int minW = INT_MAX;
  49. 	int maxW = INT_MIN;
  50. 	if(threshold==0)
  51. 	return -1;
  52. 	for(int i=0;i<edges.size();i++)
  53. 	{
  54. 		if(minW>edges[i][2])
  55. 			minW = edges[i][2];
  56.  
  57. 		if(maxW<edges[i][2])
  58. 			maxW = edges[i][2];
  59. 	}
  60. 	//cout<<"min max are "<<min<<max;
  61. 	int ans =-1;
  62. 	while(minW<=maxW)
  63. 	{
  64. 		int mid = (minW+maxW )/2;
  65. 		if(allNodesReachablefromZero(mid,edges,n))
  66. 		{
  67. 			ans = mid;
  68. 			maxW = mid-1;
  69. 		}
  70. 		else
  71. 		{
  72. 			minW = mid+1;
  73. 		}
  74. 	}
  75. 	return ans;
  76. }
  77. int main() {
  78. 	// your code goes here
  79. 	vector<vector<int>> test1 = {{1,0,1},{2,0,2},{3,0,1},{4,3,1},{2,1,1}};
  80. 	vector<vector<int>> test2 = {{0,1,1},{0,2,2},{0,3,1},{0,4,1},{1,2,1},{1,4,1}};
  81. 	cout<<maxWeight(5,2,test1);
  82. 	cout<<"\n";
  83. 	cout<<maxWeight(5,2,test2);
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
-1
https://ideone.com/XdHkm4
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!