fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> PII;
  5.  
  6. const int MAX_N = 1e4+5;
  7. const int MAX_MASK = 1030;
  8. const int inf = 1e9;
  9.  
  10. struct Edge {
  11.     int to;
  12.     vector<int> swords;
  13. };
  14.  
  15. int n, m, d, k;
  16.  
  17. vector<Edge> G[MAX_N];
  18. int dist[MAX_N][MAX_MASK];
  19.  
  20. int ans[15];
  21.  
  22. /*int get_new_mask(int mask_length, int mask, Edge e) {
  23.     int new_mask = mask;
  24.  
  25.     for (int bit = 0; bit < mask_length; bit++) {
  26.         if (new_mask & (1 << bit)) {
  27.             continue;
  28.         }
  29.  
  30.         if (e.swords[bit] >= ans[bit]) {
  31.             new_mask |= (1 << bit);
  32.         }
  33.     }
  34.  
  35.     return new_mask;
  36. }*/
  37.  
  38. vector<int> get_new_mask_list(int mask_length, int mask, Edge e) {
  39.     vector<int> bits_to_improve;
  40.  
  41.     for (int bit = 0; bit < mask_length; bit++) {
  42.         if (mask & (1 << bit)) {
  43.             continue;
  44.         }
  45.  
  46.         if (e.swords[bit] >= ans[bit]) {
  47.             bits_to_improve.push_back(bit);
  48.         }
  49.     }
  50.  
  51.     vector<int> new_mask_list;
  52.  
  53.     int len = (int)bits_to_improve.size();
  54.     for (int tmp_mask = 0; tmp_mask < (1 << len); tmp_mask++) {
  55.         int new_mask = mask;
  56.  
  57.         for (int i = 0; i < len; i++) {
  58.             if (tmp_mask & (1 << i)) {
  59.                 new_mask |= (1 << bits_to_improve[i]);
  60.             }
  61.         }
  62.  
  63.         new_mask_list.push_back(new_mask);
  64.     }
  65.  
  66.     return new_mask_list;
  67. }
  68.  
  69. bool check(int index) {
  70.     int mask_length = index + 1;
  71.  
  72.     for (int i = 1; i <= n; i++) {
  73.         for (int mask = 0; mask < (1 << mask_length); mask++) {
  74.             dist[i][mask] = inf;
  75.         }
  76.     }
  77.     dist[1][0] = 0;
  78.  
  79.     queue<PII> Q;
  80.     Q.push(make_pair(1, 0));
  81.  
  82.     while (!Q.empty()) {
  83.         PII tmp = Q.front();
  84.         Q.pop();
  85.  
  86.         int v = tmp.first;
  87.         int mask = tmp.second;
  88.  
  89.         for (Edge e: G[v]) {
  90.             int to = e.to;
  91.             //int new_mask = get_new_mask(mask_length, mask, e);
  92.  
  93.             vector<int> new_mask_list = get_new_mask_list(mask_length, mask, e);
  94.  
  95.             for (int new_mask: new_mask_list) {
  96.                 if (dist[to][new_mask] > dist[v][mask] + 1) {
  97.                     dist[to][new_mask] = dist[v][mask] + 1;
  98.                     Q.push(make_pair(to, new_mask));
  99.                 }
  100.             }
  101.         }
  102.     }
  103.  
  104.     int full_mask = 0;
  105.     for (int bit = 0; bit < mask_length; bit++) {
  106.         full_mask |= (1 << bit);
  107.     }
  108.  
  109.     return dist[n][full_mask] <= d;
  110. }
  111.  
  112. int main() {
  113.     ios_base::sync_with_stdio(0);
  114.     cin.tie(0);
  115.  
  116.     cin >> n >> m >> d >> k;
  117.     for (int i = 0; i < n; i++) {
  118.         int u, v;
  119.         cin >> u >> v;
  120.  
  121.         Edge e1, e2;
  122.         e1.to = u;
  123.         e2.to = v;
  124.  
  125.         for (int j = 0; j < k; j++) {
  126.             int s;
  127.             cin >> s;
  128.             e1.swords.push_back(s);
  129.             e2.swords.push_back(s);
  130.         }
  131.  
  132.         G[u].push_back(e2);
  133.         G[v].push_back(e1);
  134.     }
  135.  
  136.     for (int i = 0; i < k; i++) {
  137.         int l = 0;
  138.         int r = inf;
  139.  
  140.         while (l < r) {
  141.             int mid = (l + r + 1) / 2;
  142.             ans[i] = mid;
  143.  
  144.             if (check(i)) {
  145.                 l = mid;
  146.             } else {
  147.                 r = mid - 1;
  148.             }
  149.         }
  150.  
  151.         ans[i] = l;
  152.     }
  153.  
  154.     for (int i = 0; i < k; i++) {
  155.         cout << ans[i] << ' ';
  156.     }
  157.  
  158.  
  159.     return 0;
  160. }
  161.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
7 7 6 2
1 2 7 9
2 7 1 0
1 3 5 6
3 4 10 1
4 7 0 0
5 6 2 17
5 7 3 15
stdout
copy 
10 15
https://ideone.com/tsfSoG
language:
C++14 (gcc 8.3)
created:
16 days 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!