Advertisement
Guest User

Untitled

a guest
Dec 17th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.72 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #define pb push_back
  5. #define sc second
  6. #define fs first
  7.  
  8.  
  9. using namespace std;
  10.  
  11. typedef long long lli;
  12.  
  13. struct trine{
  14. int a;
  15. int b;
  16. int c;
  17. trine(int a1, int b2, int c3){
  18. a = a1;
  19. b = b2;
  20. c = c3;
  21. }
  22. trine () {
  23. a = 0;
  24. b = 0;
  25. c = 0;
  26. }
  27. bool operator< (trine other){
  28. if (other.a < a){return false;
  29. }
  30. if ((other.a == a)&&(other.b < b)){
  31. return false;
  32. }
  33. if (((other.a == a)&&(other.b == b))&&( other.c < c)){
  34. return false;
  35. }
  36. return true;
  37. }
  38. };
  39. const int maxn = 1e5+5;
  40. int sp[maxn], p[maxn], sz[maxn];
  41. int ans = 0, k;
  42. int get (int v){
  43. if (p[v] == v){return v;}
  44. return p[v] = get(p[v]);
  45. }
  46. void unite (int v , int u , int wei){
  47. v = get(v);
  48. u = get(u);
  49. if (v != u){
  50. if (sz[u] < sz[v]){swap(v,u);}
  51. p[v] = u;
  52. sz[u] += sz[v];
  53. sp[u] += sp[v];
  54. if (sp[u] == k){
  55. ans = wei;
  56. }
  57. }
  58. }
  59.  
  60. int main() {
  61. ios_base::sync_with_stdio(false);
  62. cin.tie(0);
  63. int n, m, x, y, z;
  64. cin >> n >> m >> k;
  65. for (int i = 0; i <= n; ++i){
  66. p[i] = i;
  67. sz[i] = 1;
  68. }
  69. for (int i = 0 ; i < k; ++i){
  70. cin >> x;
  71. sp[x] = 1;
  72. }
  73. vector <trine> e(m);
  74. for (int i = 0; i < m; ++i){
  75. cin >> x >> y >> z;
  76. e[i] = trine(z, x, y);
  77. }
  78. sort(e.begin(), e.end());
  79. for (auto k : e){
  80. unite(k.b, k.c, k.a);
  81. if (ans != 0){
  82. break;
  83. }
  84. }
  85. for (int i = 0; i < k; ++i){
  86. cout << ans << ' ';
  87. }
  88. return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement