Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdafx.h"
- #include <algorithm>
- #include <iostream>
- #include <queue>
- #include <set>
- #include <vector>
- #include <map>
- using namespace std;
- map<set<int>, vector<pair<int, int > > > graph;
- class comp
- {
- public:
- bool operator() (const pair<int, set<int> >& p1, const pair<int, set<int> >& p2) const
- {
- return p1.first > p2.first;
- }
- };
- int main() {
- int N, p, x, K, len;
- cin >> N;
- for (int t = 0; t < N; t++) {
- cin >> p;
- for (int j = 0; j<p; j++)
- {
- cin >> len >> K;
- set<int> req;
- for (int k = 0; k<K; k++) {
- cin >> x;
- req.insert(x);
- }
- graph[req].push_back(make_pair(len, t));
- }
- }
- priority_queue<pair<int, set<int> >, vector<pair<int, set<int> > >, comp> Q;
- for (auto s : graph[set<int>()]) { Q.push(make_pair(s.first, set<int> { s.second })); }
- while (!Q.empty()) {
- set<int> dis = Q.top().second;
- int c_prio = Q.top().first;
- Q.pop();
- if (dis.count(0) != 0) {
- cout << c_prio << '\n';
- break;
- }
- for (auto p : graph[dis]) {
- set<int> next;
- next.insert(p.second);
- Q.push(make_pair(c_prio + p.first, next));
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement