fork download 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define pii pair<int,int>
  4. #define fi first
  5. #define int long long
  6. #define se second
  7. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define TXT "test"
  9. #define dn cout<<"\n";
  10. #define freo if(fopen(TXT".inp","r")){freopen(TXT".inp","r",stdin); freopen(TXT".out","w",stdout);}             ///TEMPLATE MADE BY NIETTRAAN
  11. using namespace std;
  12.  
  13.  
  14.  
  15. const int MXN = 1 * 1e6 + 5;
  16. const int INF = 1e18;
  17. const int MOD = 1e9+7;
  18. const int LOG = 20;
  19.  
  20. int n, m, a, b;
  21. bool c[MXN];
  22. struct NT
  23. {
  24.     int x, y, t;
  25. }  niet[MXN];
  26. int dist[MXN];
  27. vector<pii> nucy[MXN];
  28.  
  29. void sub1()
  30. {
  31.     memset(dist, 0x3f, sizeof dist);
  32.     dist[1] = 0;
  33.  
  34.     priority_queue<pii, vector<pii>, greater<>> pq;
  35.     pq.push({0, 1});
  36.     int sum = a + b, phi, dtime;
  37.     while (!pq.empty()) {
  38.         auto [time, u] = pq.top();
  39.         pq.pop();
  40.         if (time > dist[u]) continue;
  41.  
  42.         if (u == n) {
  43.             cout << time;
  44.             return;
  45.         }
  46.  
  47.         for (auto [W, v] : nucy[u])
  48.         {
  49.             if (W > a) continue;
  50.             phi = time % sum;
  51.  
  52.             if (phi <= a - W)
  53.                 dtime = time;
  54.             else
  55.                 dtime = (time / sum + 1) * sum;
  56.  
  57.             int artime = dtime + W;
  58.  
  59.             if (artime < dist[v]) {
  60.                 dist[v] = artime;
  61.                 pq.push({artime, v});
  62.             }
  63.         }
  64.     }
  65.  
  66.     cout << -1;
  67. }
  68.  
  69.  
  70. void sub2()
  71. {
  72.     memset(dist, 0x3f, sizeof dist);
  73.     dist[1] = 0;
  74.  
  75.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  76.     pq.push({0, 1});
  77.  
  78.     while(!pq.empty())
  79.     {
  80.         auto [W, u] = pq.top();
  81.         pq.pop();
  82.  
  83.         if (W != dist[u]) continue;
  84.  
  85.         for(auto [w, v] : nucy[u])
  86.         {
  87.             if(dist[u] + w < dist[v])
  88.             {
  89.                 dist[v] = dist[u] + w;
  90.                 pq.push({dist[v], v});
  91.             }
  92.         }
  93.     }
  94.  
  95.     if(dist[n] > a)
  96.     {
  97.         cout << -1;
  98.         return;
  99.     }
  100.     cout << dist[n];
  101. }
  102.  
  103. void sub3()
  104. {
  105.     if (a < 10)
  106.     {
  107.         cout << -1;
  108.         return;
  109.     }
  110.     memset(dist, 0x3f, sizeof dist);
  111.     dist[1] = 0;
  112.     priority_queue<pii,vector<pii>,greater<pii>> pq;
  113.     pq.push({0, 1});
  114.  
  115.     int sum = a + b, phi, dtime, artime;
  116.  
  117.     while(!pq.empty())
  118.     {
  119.         auto [time, u] = pq.top();
  120.         pq.pop();
  121.         if (time > dist[u]) 
  122.             continue;
  123.  
  124.         if (u == n)
  125.         {
  126.             cout << time;
  127.             return;
  128.         }
  129.  
  130.         for (auto [W, v] : nucy[u])
  131.         {
  132.             phi = time % sum;
  133.             if (phi <= a - W)
  134.                 dtime = time;
  135.             else
  136.                 dtime = (time / sum + 1) * sum;
  137.             artime = dtime + W;
  138.             if (artime < dist[v])
  139.             {
  140.                 dist[v] = artime;
  141.                 pq.push({artime, v});
  142.             }
  143.         }
  144.     }
  145.  
  146.     cout << -1;
  147. }
  148.  
  149.  
  150. void solve()
  151. {
  152.     bool checksub2 = 1, checksub3 = 1;
  153.     cin >> n >> m;
  154.     for(int i = 1; i <= m; i -= -1)
  155.     {
  156.         cin >>  niet[i].x >>  niet[i].y >>  niet[i].t;
  157.         nucy[niet[i].x].pb({niet[i].t, niet[i].y});
  158.         if(niet[i].t != 10)
  159.         {
  160.             checksub3 = 0;
  161.         }
  162.     }
  163.     for(int i = 1; i <= n; i -= -1)
  164.     {
  165.         cin >> c[i];
  166.         if(i > 2 && i < n && c[i] == 0)
  167.         {
  168.             checksub2 = 0;
  169.         }
  170.     }
  171.     cin >> a >> b;
  172.     if(n <= 5 && m <= 10)
  173.     {
  174.         sub1();
  175.         return;
  176.     }
  177.     if(checksub2)
  178.     {
  179.         sub2();
  180.         return;
  181.     }
  182.     if(checksub3)
  183.     {
  184.         sub3();
  185.         return;
  186.     }
  187. }
  188.  
  189. int32_t main()
  190. {
  191.     ios;
  192.     freo;
  193.     solve();
  194.     return 0;
  195. }
  196. /*
  197.  
  198. */
  199.  
Success #stdin #stdout 0.01s 36292KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/PFTOJP
language:
C++ (gcc 8.3)
created:
4 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!