fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  10. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  11. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  12. #define fi first
  13. #define se second
  14. #define M 1000000007
  15. #define MAXN 201
  16. #define INF (1ll<<60)
  17. #define BLOCK_SIZE 425
  18. #define MAX_NODE 1001001
  19. #define LOG 19
  20. #define ALPHA_SIZE 26
  21. #define BASE 311
  22. #define NAME "file"
  23. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  24. using namespace std;
  25. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  26. const ll NMOD = 1;
  27. const int dx[] = {-1, 0, 1,0};
  28. const int dy[] = {0, 1, 0, -1};
  29. //**Variable**//
  30. ll n, m, p, k   ;
  31. ll arr[MAXN];
  32. ll d[MAXN][(1<<13)+1] ;
  33. vector<ll> kiem[MAXN];
  34. //**Struct**//
  35. struct Edge {
  36.     ll v,w ;
  37.     vector<ll> dragon ;
  38.     Edge(ll a,ll b, vector<ll> temp ) {
  39.         v = a;
  40.         w = b ;
  41.         dragon = temp ;
  42.     }
  43. };
  44. vector<Edge>adj[MAXN] ;
  45. struct Data {
  46.     ll u,w, mask ;
  47.     bool operator < (const Data & other) const {
  48.         return w > other.w;
  49.     }
  50. };
  51. //**Function**//
  52. template<class X, class Y >
  53. bool minimize(X & x, const Y &y ) {
  54.     return x > y ? x = y, 1:0 ;
  55. }
  56. template<class X, class Y >
  57. bool maximize(X &x, const Y &y ) {
  58.     return x < y ? x = y, 1:0 ;
  59. }
  60. bool check(ll mask1, ll mask2 ) {
  61.     FOR(i, 0, p -1 ) {
  62.         if(mask2 >> i & 1 ) {
  63.             if(!( mask1>> i &1) ) return false;
  64.         }
  65.     }
  66.     return true;
  67. }
  68. void init() {
  69.     cin>>n>>m >> p >> k ; // lần lượt là số thành phố, số con đường, số loại rồng và số thợ rèn
  70.     FOR(i, 1, k ) {
  71.         ll pos, cnt ;
  72.         cin>> pos >> cnt ;
  73.         FOR(j, 1, cnt ) {
  74.             ll x;
  75.             cin >>x ;
  76.             kiem[pos].push_back(x- 1 ) ;
  77.         }
  78.     }
  79.     FOR(i, 1,m) {
  80.         ll x, y, w,  cnt ;
  81.         cin >> x>> y >> w >> cnt ;
  82.         vector<ll>temp ;
  83.         FOR(j, 1, cnt  ) {
  84.             ll t;
  85.             cin >> t;
  86.             temp.push_back(t-1) ;
  87.         }
  88.         adj[x].push_back(Edge(y, w,temp)) ;
  89.         adj[y].push_back(Edge(x, w,temp)) ;
  90.     }
  91. }
  92. void dijkstra(ll start ) {
  93.     FOR(i, 0, n ) FOR(mask, 0, (1<<p) - 1 ) d[i][mask] = INF ;
  94.     ll temp_mask = 0 ;
  95.     for(ll cur : kiem[start]) temp_mask |= (1 << cur) ;
  96.     d[start][temp_mask] = 0 ;
  97.     priority_queue<Data>pq ;
  98.     pq.push({start,  0, temp_mask}) ;
  99.     while(!pq.empty()) {
  100.         Data u = pq.top() ;
  101.         pq.pop() ;
  102.         if(d[u.u][u.mask] < u.w ) continue ;
  103.         for(Edge v : adj[u.u]) {
  104.             ll need_mask = 0 , new_mask = 0  ;
  105.             for(ll it: v.dragon) need_mask |= (1<< it);
  106.             if(!check(u.mask , need_mask )) continue;
  107.              for(ll it : kiem[v.v]) new_mask |= (1<< it ) ;
  108.              new_mask |= u.mask ;
  109.              if(d[v.v][new_mask] > v.w + u.w) {
  110.                 pq.push({v.v , d[v.v][new_mask] = v.w + u.w , new_mask }) ;
  111.              }
  112.         }
  113.     }
  114. }
  115. void solve() {
  116.     dijkstra(1);
  117.     ll ans = INF ;
  118.     FOR(mask, 0, (1<<p)-1 ) minimize(ans,d[n][mask]) ;
  119.     cout << (ans == INF ? -1 : ans ) ;
  120. }
  121.  
  122. __ROOT__ {
  123. //     freopen(NAME".inp" , "r" , stdin);
  124. //     freopen(NAME".out" , "w", stdout) ;
  125.     fast;
  126.     int t =1 ;//    cin >> t;
  127.     while(t-- ) {
  128.         init();
  129.         solve();
  130.     }
  131. }
  132.  
  133.  
  134.  
  135.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 7 4 2 
2 1 2 
3 2 1 3 
1 2 2 0 
2 3 9 0 
1 4 2 1 2 
2 5 3 0 
4 5 5 2 2 3 
4 6 18 0 
5 6 3 2 1 2
stdout
copy 
24
https://ideone.com/CPxsHj
language:
C++14 (clang 8.0)
created:
190 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!