fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. #define fast ios::sync_with_stdio(false); cin.tie(nullptr); cin.tie(nullptr);
  4. #define ll long long
  5.  
  6. using namespace std;
  7.  
  8. class graph {
  9. 	unordered_map<ll, list<ll>> adjList;
  10.  
  11.   public:
  12.  
  13. 	void insert(ll u, ll v) {
  14. 		adjList[u].push_front(v);
  15. 		adjList[v].push_front(u);
  16. 	}
  17.  
  18. 	ll bfs(ll src, vector<ll>& visited) {
  19.  
  20. 		queue<ll> q;
  21. 		ll roads = 0;
  22. 		visited[src] = true;
  23. 		q.push(src);
  24.  
  25. 		while (!q.empty()) {
  26. 			ll node = q.front();
  27. 			q.pop();
  28.  
  29. 			for (auto padosi : adjList[node]) {
  30. 				if (!visited[padosi]) {
  31. 					visited[padosi] = true;
  32. 					q.push(padosi);
  33. 					roads++;
  34. 				}
  35. 			}
  36. 		}
  37.  
  38. 		return roads;
  39. 	}
  40.  
  41. 	ll religiousPeople(ll n, ll tempCost, ll roadCost) {
  42. 		if (tempCost < roadCost)
  43. 			return (tempCost * n);
  44.  
  45. 		ll cost = 0;
  46. 		vector<ll> visited(n + 1, false);
  47.  
  48. 		for (auto ele : adjList) {
  49. 			ll node = ele.first;
  50. 			if (!visited[node]) {
  51. 				cost += (bfs(node, visited) * roadCost) + tempCost;
  52. 			}
  53. 		}
  54.  
  55. 		for (ll i = 1; i <= n; i++)
  56. 			if (!visited[i])
  57. 				cost += tempCost;
  58.  
  59. 		return cost;
  60. 	}
  61. };
  62. int main() {
  63. 	fast
  64. 	ll t;
  65. 	cin >> t;
  66. 	while (t--) {
  67. 		graph g;
  68. 		ll n, e, tempCost, roadCost;
  69. 		cin >> n >> e >> tempCost >> roadCost;
  70. 		while (e--) {
  71. 			ll u, v;
  72. 			cin >> u >> v;
  73. 			g.insert(u, v);
  74. 		}
  75. 		cout << g.religiousPeople(n, tempCost, roadCost) << endl;
  76. 	}
  77.  
  78. }
Success #stdin #stdout 0s 4252KB
comments (?)
stdin 
2
3 3 2 1
1 2
3 1
2 3
6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6
stdout 
4
12
https://ideone.com/bvQQnw
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!