fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 1e9 + 7;
  6.  
  7. struct Droga {
  8.     int cel;
  9.     int czas;
  10.     int potwory;
  11. };
  12.  
  13. struct Stan {
  14.     int czas;
  15.     int w;
  16.     int miecze;
  17.  
  18.     bool operator>(const Stan& inny) const {
  19.         return czas > inny.czas;
  20.     }
  21. };
  22.  
  23. int main() {
  24.     ios_base::sync_with_stdio(0);
  25.     cin.tie(0);
  26.  
  27.     int n, m, p, k;
  28.     if (!(cin >> n >> m >> p >> k)) return 0;
  29.  
  30.     vector<int> kowal(n + 1, 0);
  31.     for (int i = 0; i < k; ++i) {
  32.         int w, q;
  33.         cin >> w >> q;
  34.         int maska = 0;
  35.         for (int j = 0; j < q; ++j) {
  36.             int r;
  37.             cin >> r;
  38.             maska |= (1 << (r - 1));
  39.         }
  40.         kowal[w] |= maska;
  41.     }
  42.  
  43.     vector<vector<Droga>> graf(n + 1);
  44.     for (int i = 0; i < m; ++i) {
  45.         int v, w, t, s;
  46.         cin >> v >> w >> t >> s;
  47.         int maska_potworow = 0;
  48.         for (int j = 0; j < s; ++j) {
  49.             int u;
  50.             cin >> u;
  51.             maska_potworow |= (1 << (u - 1));
  52.         }
  53.         graf[v].push_back({w, t, maska_potworow});
  54.         graf[w].push_back({v, t, maska_potworow});
  55.     }
  56.  
  57.     vector<vector<int>> odl(n + 1, vector<int>(1 << p, INF));
  58.     priority_queue<Stan, vector<Stan>, greater<Stan>> kolejka;
  59.  
  60.     int start_miecze = kowal[1];
  61.     odl[1][start_miecze] = 0;
  62.     kolejka.push({0, 1, start_miecze});
  63.  
  64.     int wynik = -1;
  65.  
  66.     while (!kolejka.empty()) {
  67.         Stan akt = kolejka.top();
  68.         kolejka.pop();
  69.  
  70.         if (akt.czas > odl[akt.w][akt.miecze]) continue;
  71.  
  72.         if (akt.w == n) {
  73.             wynik = akt.czas;
  74.             break;
  75.         }
  76.  
  77.         for (auto& krawedz : graf[akt.w]) {
  78.             if ((akt.miecze & krawedz.potwory) == krawedz.potwory) {
  79.                 int nowe_miecze = akt.miecze | kowal[krawedz.cel];
  80.                 if (akt.czas + krawedz.czas < odl[krawedz.cel][nowe_miecze]) {
  81.                     odl[krawedz.cel][nowe_miecze] = akt.czas + krawedz.czas;
  82.                     kolejka.push({odl[krawedz.cel][nowe_miecze], krawedz.cel, nowe_miecze});
  83.                 }
  84.             }
  85.         }
  86.     }
  87.  
  88.     cout << wynik << "\n";
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
2 1 1 1
2 1 1
1 2 1 1 1
stdout
copy 
-1
https://ideone.com/8HyfyB
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!