fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define pb push_back
  6. #define S second
  7. #define F first
  8. #define f(i, n) for (int i = 1; i <= n; i++)
  9. #define fast                      \
  10.     ios_base::sync_with_stdio(0); \
  11.     cin.tie(0);                   \
  12.     cout.tie(0)
  13. #define vi vector<int>
  14. #define pii pair<int, int>
  15.  
  16. const int N = 305;
  17. const int inf = 1e12;
  18. const int mx = 1000;
  19.  
  20. vector<int> g[N];
  21. bool locate[N][N];
  22. int dis[N][N];
  23. vector<vector<int>> recipe[N];
  24. int dp[N][N];
  25.  
  26. int n, m, s, r;
  27.  
  28. //city i,stone j
  29.  
  30. int go(int i, int j)
  31. {
  32.     int &ans = dp[i][j];
  33.  
  34.     if (ans != -1)
  35.         return ans;
  36.  
  37.     int res = inf;
  38.  
  39.     if (locate[i][j] == 1)
  40.         return res = 0;
  41.  
  42.     f(l, n) if (l != i) res = min(res, go(l, j) + dis[l][i]);
  43.  
  44.     for (auto vv : recipe[j])
  45.     {
  46.         int temp = 0;
  47.  
  48.         for (auto v : vv)
  49.         {
  50.             int temp2 = inf;
  51.  
  52.             f(l, n) temp2 = min(temp2, go(l, v) + dis[i][l]);
  53.  
  54.             temp += temp2;
  55.         }
  56.  
  57.         res = min(res, temp);
  58.     }
  59.  
  60.     return ans = res;
  61. }
  62.  
  63. void solve()
  64. {
  65.     cin >> n >> m >> s >> r;
  66.  
  67.     int u, v;
  68.  
  69.     while (m--)
  70.     {
  71.         cin >> u >> v;
  72.         g[u].pb(v);
  73.         g[v].pb(u);
  74.     }
  75.  
  76.     //calculate distance
  77.  
  78.     f(i, n)
  79.     {
  80.         f(j, n) dis[i][j] = mx;
  81.  
  82.         vector<bool> vis(n, 0);
  83.  
  84.         vis[i] = 1;
  85.         dis[i][i] = 0;
  86.  
  87.         queue<int> q;
  88.         q.push(i);
  89.  
  90.         while (!q.empty())
  91.         {
  92.             auto x = q.front();
  93.             q.pop();
  94.  
  95.             for (auto v : g[x])
  96.                 if (!vis[v])
  97.                 {
  98.                     vis[v] = 1;
  99.                     q.push(v);
  100.                     dis[i][v] = dis[i][x] + 1;
  101.                 }
  102.         }
  103.     }
  104.  
  105.     f(i, n)
  106.     {
  107.         cin >> u;
  108.  
  109.         f(j, u)
  110.         {
  111.             cin >> v;
  112.             locate[i][v] = 1;
  113.         }
  114.     }
  115.  
  116.     f(i, r)
  117.     {
  118.         vi go;
  119.  
  120.         cin >> u;
  121.  
  122.         f(j, u)
  123.         {
  124.             cin >> v;
  125.             go.pb(v);
  126.         }
  127.  
  128.         cin >> v;
  129.  
  130.         recipe[v].push_back(go);
  131.     }
  132.  
  133.     f(i, n) f(j, s) dp[i][j] = -1;
  134.  
  135.     int res = inf;
  136.  
  137.     f(i, n) res = min(res, go(i, 1));
  138.  
  139.     if (res >= 1e12)
  140.         res = -1;
  141.  
  142.     cout << res << '\n';
  143.  
  144.     for (int i = 0; i < N; i++)
  145.     {
  146.         g[i].clear();
  147.         for (int j = 0; j < N; j++)
  148.             locate[i][j] = 0;
  149.         recipe[i].clear();
  150.     }
  151. }
  152.  
  153. signed main()
  154. {
  155.     fast;
  156.  
  157.     int t = 1;
  158.  
  159.     cin >> t;
  160.  
  161.     for (int i = 1; i <= t; i++)
  162.     {
  163.         cout << "Case #" << i << ": ";
  164.         solve();
  165.     }
  166. }
  167.  
Success #stdin #stdout 0s 4476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1: -1
https://ideone.com/BA74kn
language:
C++14 (gcc 8.3)
created:
3 years 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!