Advertisement
Guest User

Untitled

a guest
May 21st, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #define INFINIT 1000000000
  4. using namespace std;
  5.  
  6. ifstream fin("zapada.in");
  7. ofstream fout("zapada.out");
  8.  
  9. struct muchie
  10. {
  11. int i,j,cost,ok;
  12. };
  13.  
  14. int n, m, t[105];
  15.  
  16. muchie x[5000];
  17. int v[5000],aux,K;
  18.  
  19. int main()
  20. {
  21. fin >> n >> m;
  22.  
  23. for(int i = 0 ; i < m ; ++i)
  24. fin >> x[i].i >> x[i].j >> x[i].cost;
  25. fin>>K;
  26. for(int i=0; i<K; i++)
  27. {
  28. fin>>aux;
  29. x[aux-1 ].ok=1;
  30. }
  31.  
  32. for(int i = 0 ; i < m - 1; i ++)
  33. for(int j = i + 1 ; j < m ; ++j)
  34. {
  35. if(x[i].ok<x[j].ok)
  36. {
  37. muchie aux=x[i];
  38. x[i]=x[j];
  39. x[j]=aux;
  40. }
  41. if(x[i].cost > x[j].cost && x[i].ok==x[j].ok)
  42. {
  43. muchie aux = x[i];
  44. x[i] = x[j];
  45. x[j] = aux;
  46. }
  47. }
  48.  
  49. for(int i =1 ; i <= n ; ++i)
  50. t[i] = i;
  51. int S = 0, cnt = 0;
  52. for(int i = 0 ; i < m && cnt < n ; i ++)
  53. if(t[x[i].i] != t[x[i].j] ||x[i].ok==1)
  54. {
  55. v[i] = 1;
  56. S += x[i].cost;
  57. int ai = t[x[i].i], aj = t[x[i].j];
  58. for(int j =1 ; j <= n ; ++j)
  59. if(t[j] == aj)
  60. t[j] = ai;
  61. }
  62. fout << S << "\n";
  63. /*for(int i = 0 ; i < m ; ++i)
  64. if(v[i] == 1)
  65. fout << x[i].i << " " << x[i].j << "\n";*/
  66. return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement