Advertisement
Guest User

Untitled

a guest
Nov 18th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.16 KB | None | 0 0
  1. #include "stdafx.h"
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <queue>
  5. #include <set>
  6. #include <vector>
  7. #include <map>
  8.  
  9.  
  10. using namespace std;
  11.  
  12.  
  13.  
  14. map<set<int>, vector<pair<int, int > > > graph;
  15.  
  16. class comp
  17. {
  18. public:
  19. bool operator() (const pair<int, set<int> >& p1, const pair<int, set<int> >& p2) const
  20. {
  21. return p1.first > p2.first;
  22. }
  23. };
  24.  
  25.  
  26. int main() {
  27.  
  28. int N, p, x, K, len;
  29. cin >> N;
  30. for (int t = 0; t < N; t++) {
  31. cin >> p;
  32. for (int j = 0; j<p; j++)
  33. {
  34. cin >> len >> K;
  35. set<int> req;
  36. for (int k = 0; k<K; k++) {
  37. cin >> x;
  38. req.insert(x);
  39. }
  40.  
  41. graph[req].push_back(make_pair(len, t));
  42. }
  43. }
  44.  
  45. priority_queue<pair<int, set<int> >, vector<pair<int, set<int> > >, comp> Q;
  46. for (auto s : graph[set<int>()]) { Q.push(make_pair(s.first, set<int> { s.second })); }
  47.  
  48. while (!Q.empty()) {
  49.  
  50. set<int> dis = Q.top().second;
  51. int c_prio = Q.top().first;
  52. Q.pop();
  53.  
  54. if (dis.count(0) != 0) {
  55. cout << c_prio << '\n';
  56. break;
  57. }
  58.  
  59. for (auto p : graph[dis]) {
  60.  
  61. set<int> next;
  62. next.insert(p.second);
  63. Q.push(make_pair(c_prio + p.first, next));
  64. }
  65.  
  66.  
  67.  
  68. }
  69.  
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement