fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. Problem: Minimum Path Cost with One Free Continuous Segment
  6.  
  7. You are given a directed weighted graph with N nodes numbered from 0 to N - 1.
  8. Each edge is given as:
  9. [u, v, w] which means there is a directed edge from node u to node v with weight w.
  10.  
  11. You want to travel from node 0 to node N - 1 with minimum possible total cost.
  12.  
  13. ------------------------------------------------------------
  14.  
  15. Special ability:
  16. You are allowed to use a special override at most once.
  17.  
  18. If you use it:
  19. - you choose one continuous block of edges on your path
  20. - that block can contain at most K edges
  21. - every edge inside that block becomes free
  22.  
  23. Important rules:
  24. - the free edges must form one single continuous segment
  25. - once you stop using the override, you cannot start it again
  26. - you may also choose not to use the override at all
  27.  
  28. ------------------------------------------------------------
  29.  
  30. Task:
  31. Return the minimum possible cost to reach node N - 1 from node 0.
  32. If there is no path, return -1.
  33.  
  34. ------------------------------------------------------------
  35.  
  36. Example 1:
  37. N = 4
  38. edges = {{0,1,5}, {1,2,7}, {2,3,4}}
  39. K = 2
  40.  
  41. Only path is:
  42. 0 -> 1 -> 2 -> 3
  43.  
  44. Normal cost = 5 + 7 + 4 = 16
  45.  
  46. If we make the first 2 edges free:
  47. 0 + 0 + 4 = 4
  48.  
  49. Answer = 4
  50.  
  51. ------------------------------------------------------------
  52.  
  53. Main idea:
  54. This is shortest path, but normal Dijkstra is not enough,
  55. because the cost also depends on whether we have started or
  56. finished using the override.
  57.  
  58. So we run Dijkstra on an expanded state space.
  59.  
  60. For every node, we keep track of the override status.
  61.  
  62. State meaning:
  63. - 0 : override has not started yet
  64. - 1..K : currently inside override, and exactly that many free edges have already been used
  65. - K + 1 : override is already finished
  66.  
  67. Transitions:
  68.  
  69. From state 0:
  70. - take next edge normally and stay in state 0
  71. - or start override on this edge, make it free, and move to state 1
  72.  
  73. From state 1..K:
  74. - stop override before taking next edge, then pay normally and move to state K+1
  75. - or continue override for free if we have used fewer than K free edges
  76.  
  77. From state K+1:
  78. - all future edges must be paid normally
  79.  
  80. Then the answer is the minimum distance among all states at node N - 1.
  81.  
  82. Time Complexity: O((N * K + M * K) log (N * K))
  83. */
  84.  
  85. class Solution {
  86. public:
  87.     long long minimumTravelCost(int n, vector<vector<int>>& edges, int k) {
  88.         vector<vector<pair<int, int>>> graph(n);
  89.  
  90.         for (auto& edge : edges) {
  91.             int u = edge[0];
  92.             int v = edge[1];
  93.             int w = edge[2];
  94.             graph[u].push_back({v, w});
  95.         }
  96.  
  97.         const long long INF = (1LL << 62);
  98.  
  99.         /*
  100.         Special case:
  101.         If k = 0, the override cannot make any edge free.
  102.         So this becomes a normal shortest path problem.
  103.         */
  104.         if (k == 0) {
  105.             vector<long long> dist(n, INF);
  106.  
  107.             priority_queue<
  108.                 pair<long long, int>,
  109.                 vector<pair<long long, int>>,
  110.                 greater<pair<long long, int>>
  111.             > pq;
  112.  
  113.             dist[0] = 0;
  114.             pq.push({0, 0});
  115.  
  116.             while (!pq.empty()) {
  117.                 auto [cost, u] = pq.top();
  118.                 pq.pop();
  119.  
  120.                 if (cost != dist[u]) continue;
  121.  
  122.                 for (auto& [v, w] : graph[u]) {
  123.                     if (dist[v] > cost + w) {
  124.                         dist[v] = cost + w;
  125.                         pq.push({dist[v], v});
  126.                     }
  127.                 }
  128.             }
  129.  
  130.             return dist[n - 1] == INF ? -1 : dist[n - 1];
  131.         }
  132.  
  133.         // For each node, we have states: 0, 1..k, k+1
  134.         int stateCount = k + 2;
  135.  
  136.         // dist[u][state] = minimum cost to reach node u in this override state
  137.         vector<vector<long long>> dist(n, vector<long long>(stateCount, INF));
  138.  
  139.         priority_queue<
  140.             tuple<long long, int, int>,
  141.             vector<tuple<long long, int, int>>,
  142.             greater<tuple<long long, int, int>>
  143.         > pq;
  144.  
  145.         // Start at node 0 without using override
  146.         dist[0][0] = 0;
  147.         pq.push({0, 0, 0});
  148.  
  149.         while (!pq.empty()) {
  150.             auto [cost, u, state] = pq.top();
  151.             pq.pop();
  152.  
  153.             if (cost != dist[u][state]) continue;
  154.  
  155.             for (auto& [v, w] : graph[u]) {
  156.  
  157.                 // Case 1: override has not started yet
  158.                 if (state == 0) {
  159.  
  160.                     // Take this edge normally
  161.                     if (dist[v][0] > cost + w) {
  162.                         dist[v][0] = cost + w;
  163.                         pq.push({dist[v][0], v, 0});
  164.                     }
  165.  
  166.                     // Start override on this edge, so this edge is free
  167.                     if (dist[v][1] > cost) {
  168.                         dist[v][1] = cost;
  169.                         pq.push({dist[v][1], v, 1});
  170.                     }
  171.                 }
  172.  
  173.                 // Case 2: currently inside the override segment
  174.                 else if (1 <= state && state <= k) {
  175.  
  176.                     // Stop override before this edge, pay normally from now on
  177.                     if (dist[v][k + 1] > cost + w) {
  178.                         dist[v][k + 1] = cost + w;
  179.                         pq.push({dist[v][k + 1], v, k + 1});
  180.                     }
  181.  
  182.                     // Continue override on this edge if limit not exceeded
  183.                     if (state < k && dist[v][state + 1] > cost) {
  184.                         dist[v][state + 1] = cost;
  185.                         pq.push({dist[v][state + 1], v, state + 1});
  186.                     }
  187.                 }
  188.  
  189.                 // Case 3: override already finished
  190.                 else {
  191.                     if (dist[v][k + 1] > cost + w) {
  192.                         dist[v][k + 1] = cost + w;
  193.                         pq.push({dist[v][k + 1], v, k + 1});
  194.                     }
  195.                 }
  196.             }
  197.         }
  198.  
  199.         long long answer = INF;
  200.  
  201.         for (int state = 0; state < stateCount; state++) {
  202.             answer = min(answer, dist[n - 1][state]);
  203.         }
  204.  
  205.         return answer == INF ? -1 : answer;
  206.     }
  207. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In member function ‘long long int Solution::minimumTravelCost(int, std::vector<std::vector<int> >&, int)’:
prog.cpp:117:22: warning: structured bindings only available with -std=c++17 or -std=gnu++17
                 auto [cost, u] = pq.top();
                      ^
prog.cpp:122:28: warning: structured bindings only available with -std=c++17 or -std=gnu++17
                 for (auto& [v, w] : graph[u]) {
                            ^
prog.cpp:150:18: warning: structured bindings only available with -std=c++17 or -std=gnu++17
             auto [cost, u, state] = pq.top();
                  ^
prog.cpp:155:24: warning: structured bindings only available with -std=c++17 or -std=gnu++17
             for (auto& [v, w] : graph[u]) {
                        ^
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/8bgSWU
language:
C++14 (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!