SHARE
TWEET

Untitled

a guest Oct 18th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <iostream>
  3. #include <map>
  4. #include <set>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int dfs(int passId, int l, int k, const int p,
  10.         const map<int, pair<vector<pair<int, int>>, vector<pair<int, int>>>>& fromEachPassToDriverAndOtherPass,
  11.         set<int>& used)
  12. {
  13.     int min_price = k;
  14.     used.insert(passId);
  15.     const auto& pass = fromEachPassToDriverAndOtherPass.at(passId);
  16.     const auto& toDrivers = pass.first;
  17.     const auto& toOthersPass = pass.second;
  18.     for (const auto& toDriver : toDrivers)
  19.     {
  20.         if (toDriver.second + l < p)
  21.             min_price -= (p - toDriver.second - l);
  22.     }
  23.     for (const auto& toOtherPass : toOthersPass)
  24.     {
  25.         if (toOtherPass.second + l < p && used.find(toOtherPass.first) == used.end())
  26.         {
  27.  
  28.             min_price = min(min_price,
  29.                             dfs(toOtherPass.first, l + toOtherPass.second, min_price, p, fromEachPassToDriverAndOtherPass,
  30.                                 used));
  31.         }
  32.     }
  33.     return min_price;
  34. }
  35.  
  36. int main()
  37. {
  38.     int m, n, p, k, s, t;
  39.     cin >> m >> n >> p >> k >> s;
  40.     map<int, pair<vector<pair<int, int>>, vector<pair<int, int>>>> fromEachPassToDriverAndOtherPass;
  41.     for (int i = 0; i < s; ++i)
  42.     {
  43.         int t1, t2, t3;
  44.         cin >> t1 >> t2 >> t3;
  45.         fromEachPassToDriverAndOtherPass[t2].first.emplace_back(t1, t3);
  46.     }
  47.     cin >> t;
  48.     for (int i = 0; i < t; ++i)
  49.     {
  50.         int t1, t2, t3;
  51.         cin >> t1 >> t2 >> t3;
  52.         fromEachPassToDriverAndOtherPass[t1].second.emplace_back(t2, t3);
  53.         fromEachPassToDriverAndOtherPass[t2].second.emplace_back(t1, t3);
  54.     }
  55.     int min_price = k;
  56.     for (const auto& pass : fromEachPassToDriverAndOtherPass)
  57.     {
  58.         int passId = pass.first;
  59.         set<int> used;
  60.         min_price = min(min_price, dfs(passId, 0, k, p, fromEachPassToDriverAndOtherPass, used));
  61.         if (min_price <= 1)
  62.         {
  63.             cout << 1;
  64.             return 0;
  65.         }
  66.     }
  67.     cout << min_price;
  68.     return 0;
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top