Advertisement
Guest User

Untitled

a guest
Sep 1st, 2015
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.24 KB | None | 0 0
  1.  
  2. //Esteban Foronda Sierra
  3. using namespace std;
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <iterator>
  7. #include <numeric>
  8. #include <sstream>
  9. #include <fstream>
  10. #include <cassert>
  11. #include <climits>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <string>
  15. #include <cstdio>
  16. #include <vector>
  17. #include <cmath>
  18. #include <queue>
  19. #include <deque>
  20. #include <stack>
  21. #include <list>
  22. #include <map>
  23. #include <set>
  24.  
  25. template <class T> string toStr(const T &x)
  26. { stringstream s; s << x; return s.str(); }
  27. template <class T> int toInt(const T &x)
  28. { stringstream s; s << x; int r; s >> r; return r;}
  29.  
  30. #define D(x) cout << #x " is " << x << endl
  31. #define ll long long
  32. int n, m, disjoint;
  33. const int MAXN = 100005;
  34. int p[MAXN];
  35.  
  36. void initialize(){
  37. for (int i = 0; i <= n; ++i) p[i] = i;
  38. }
  39.  
  40. int find(int u){
  41. if (p[u] == u) return u;
  42. return p[u] = find(p[u]);
  43. }
  44.  
  45. void join(int u, int v){
  46. int a = find(u);
  47. int b = find(v);
  48. if (a == b) return;
  49. p[a] = b;
  50. }
  51.  
  52. struct edge{
  53. int start, end;
  54. ll weight;
  55. edge(int u, int v, ll w){
  56. start = u; end = v; weight = w;
  57. }
  58. bool operator < (const edge &other) const{
  59. return weight < other.weight;
  60. }
  61. };
  62.  
  63. vector <edge> edges;
  64.  
  65. ll kruskal(){
  66. initialize();
  67. sort(edges.begin(), edges.end());
  68. ll total = 0LL;
  69. for (int i = 0; i < edges.size(); ++i){
  70. int u = edges[i].start;
  71. int v = edges[i].end;
  72. ll w = edges[i].weight;
  73. if (find(u) != find(v)){
  74. disjoint--;
  75. total += w;
  76. join(u, v);
  77. }
  78. }
  79. return total;
  80. }
  81.  
  82. int main() {
  83. while(cin >> n >> m && n && m) {
  84. map<string, int> cities;
  85. disjoint = n - 1;
  86. edges.clear();
  87. for(int i = 0; i < n; ++i) {
  88. string name;
  89. cin >> name;
  90. cities[name] = i;
  91. }
  92. for(int i = 0; i < m; ++i) {
  93. string su, sv;
  94. ll weight;
  95. cin >> su >> sv >> weight;
  96. int u = cities[su];
  97. int v = cities[sv];
  98. edges.push_back(edge(u, v, weight));
  99. }
  100. string start;
  101. cin >> start;
  102. ll ans = kruskal();
  103. if(!disjoint) cout << ans << endl;
  104. else cout << "Impossible" << endl;
  105. }
  106. return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement