Advertisement
Guest User

Untitled

a guest
Dec 17th, 2018
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.99 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/stack:200000000")
  3. #pragma GCC optimize("Ofast")
  4. #pragma GCC optimize("unroll-loops")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6.  
  7. #include <set>
  8. #include <map>
  9. #include <deque>
  10. #include <cmath>
  11. #include <queue>
  12. #include <random>
  13. #include <bitset>
  14. #include <time.h>
  15. #include <string>
  16. #include <chrono>
  17. #include <cstdio>
  18. #include <vector>
  19. #include <cstdlib>
  20. #include <iomanip>
  21. #include <cassert>
  22. #include <iostream>
  23. #include <algorithm>
  24. #include <unordered_map>
  25. #include <unordered_set>
  26. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  27. #define itn int
  28. //#define endl '\n'
  29. #define mp make_pair
  30. #define pbc push_back
  31. #define pob pop_back()
  32. #define empb emplace_back
  33. #define sp system("pause")
  34. #define queuel queue<long long>
  35. #define matrix vector<vector<ll>>
  36. #define all(x) (x).begin(),(x).end()
  37. #define rall(x) (x).rbegin(),(x).rend()
  38. #define pin(p) cin >> p.first >> p.second;
  39. #define rev(v) reverse(v.begin(),v.end());
  40. #define mx(v) max_element(v.begin(), v.end());
  41. #define mn(v) min_element(v.begin(), v.end());
  42. #define dig(c) (c >=' 0' && c <= '9') ? 1 : 0
  43. #define sout(s, c) for(auto i : s) cout << i << c;
  44. #define pout(p) cout << p.first << " " << p.second;
  45. #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
  46. #define vin(v) for(ll i = 0; i < v.size(); ++i) cin >> v[i];
  47. #define vout(v, c) for(int i = 0; i < v.size(); ++i) cout << v[i] << c;
  48. #define pushi(v, a) for(int i = 0; i < a.size(); ++i) v.push_back(a[i]);
  49. #define sin(s, n) for(int i = 0; i < n; ++i){int a; cin >> a; s.insert(a);}
  50. #define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
  51. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  52. using namespace std;
  53. /*▄███████▀▀▀▀▀▀███████▄
  54. ░▐████▀▒ЗАПУСКАЕМ▒▀██████▄
  55. ░███▀▒▒▒▒▒ДЯДЮ▒▒▒▒▒▒▀█████
  56. ░▐██▒▒▒▒▒БОГДАНА▒▒▒▒▒████▌
  57. ░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
  58. ░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
  59. ░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
  60. ░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
  61. ░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
  62. ░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
  63. ░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
  64. ░░░░▄██████████████▒▒▐▌
  65. ░░░▀███▀▀████▀█████▀▒▌
  66. ░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
  67. ░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐*/
  68. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  69. typedef long long ll;
  70. typedef long double ld;
  71. typedef unsigned long long ull;
  72. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  73. const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
  74. const ll inf = 1000 * 1000 * 1000;
  75. const ld PI = acos(-1.0);
  76. const ll mod1 = inf * inf + 1337 * 42 + 57 * 179 + 228;
  77. const ll mod2 = inf + 7;
  78. const ll bigmod = 1LL * inf * 100 + 3;
  79. const int MAXN = 300005;
  80. const ld EPS = 1e-10;
  81. const int N = 300228;
  82. ll hp = 1e6 + 3;
  83. ll ans = 0;
  84. struct edge
  85. {
  86. int a, b, c;
  87. };
  88. vector<int> p(MAXN);
  89. vector<int> rnk(MAXN);
  90. int na = 0;
  91. int us = 0;
  92. int c = 0;
  93. vector<int> u(MAXN);
  94. void make(int v)
  95. {
  96. p[v] = v;
  97. }
  98. int fin(int v)
  99. {
  100. return (v == p[v] ? v : p[v] = fin(p[v]));
  101. }
  102. void unite(int a, int b, int nw)
  103. {
  104. a = fin(a) ; b = fin(b);
  105. if (a^b)
  106. {
  107. if (rnk[a] < rnk[b])swap(a, b);
  108. p[b] = a;
  109. if (rnk[a] == rnk[b]) rnk[a] ++;
  110. if (u[a] && u[b])c++;
  111. if (c == us - 1)
  112. {
  113. for(int i =1;i<=us;++i)
  114. {
  115. cout << nw << ' ';
  116. }
  117. exit(0);
  118. }
  119. }
  120. }
  121. bool cmp(edge a, edge b)
  122. {
  123. return a.c < b.c;
  124. }
  125. signed main()
  126. {
  127. fastio();
  128. int n, m, k;
  129. cin >> n >> m >> k;
  130. for (int i = 0; i < k; ++i)
  131. {
  132. int x;
  133. cin >> x;
  134. u[x] = 1;
  135. }
  136. vector<edge> a;
  137. for (int i = 0; i < m; ++i)
  138. {
  139. int x, y, z;
  140. cin >> x >> y >> z;
  141. a.pbc({ x,y,z });
  142. }
  143. us = k;
  144. na = n;
  145. sort(all(a),cmp);
  146. for (int i = 1; i <= n; ++i)
  147. {
  148. make(i);
  149. if (u[i])rnk[i] = 1e8;
  150. }for (int i = 0; i < a.size(); ++i)
  151. {
  152. if (fin(a[i].a) != fin(a[i].b))
  153. {
  154. unite(a[i].a, a[i].b, a[i].c);
  155. }
  156. }
  157. sp;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement