Shortest Paths with States

A shortest-path vertex must describe everything about the past that changes future options. If one discounted edge is allowed, reaching city v with the coupon unused is different from reaching v after spending it. A single dist[v] merges these situations and can discard the optimal route. State graphs expand the vertex description while keeping the ordinary shortest-path algorithm and its proof.

Prerequisites: Dijkstra; priority queues; nonnegative weights. Difficulty: Advanced. Review: Dijkstra’s algorithm.

Build the idea

1. 1. Define sufficient state information

   Use (v,used), where used is 0 or 1. You do not need the full route: future prices depend only on the current vertex and whether the coupon remains. The expanded graph has 2n states. Distances are dist[v][0] and dist[v][1]; these are independent best costs, not a distance plus an auxiliary flag attached to one chosen route.

2. 2. Enumerate every legal transition

   For an undirected input edge v—u of nonnegative weight w, either layer may traverse it at full cost w without changing used. From layer 0 only, there is an additional transition to (u,1) costing floor(w/2). No transition restores a coupon. All expanded weights remain nonnegative, so Dijkstra applies. Generate these transitions while scanning ordinary adjacency lists; there is no need to allocate a separate expanded edge list.

3. 3. Initialize and finish precisely

   Start only dist[s][0]=0; the used layer is not initially available for free unless it arises from an actual discounted traversal. Heap entries contain distance, vertex and used. An outdated entry must be checked against dist[v][used], not dist[v][0] or a single visited[v]. Because the coupon is optional, the answer is min(dist[t][0],dist[t][1]). If exactly one use were required, inspect only layer 1; this changes s=t cases too.

4. 4. Compare routes on the sample

   Routes 1→2→4 have original costs 8+8=16; discounting one edge gives 4+8=12. Route 1→3→4 costs 3+20=23; discounting the larger edge gives 3+10=13. Dijkstra retains both coupon states at intermediate vertices and returns 12. The most expensive original route can sometimes become best after a discount, so selecting an ordinary shortest route before discounting is not valid in general.

5. 5. Transfer the method

   For a key/door problem, state may include a key bitmask. For an even number of traversed edges, use parity. For at most k special actions, use a counter 0..k. Correctness follows by a correspondence: each legal original route produces a path in the state graph with equal cost, and every state-graph path obeys the original rules. The main design challenge is sufficient state without storing irrelevant history.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<array>
#include<functional>
#include<limits>
#include<algorithm>
#include<utility>
using namespace std;
using ll=long long;
int main(){
    int n,m,s,t;
    if(!(cin>>n>>m>>s>>t)){
        return 0;
    }
    vector<vector<pair<int,ll>>>graph(n+1);
    for(int i=0;i<m;++i){
        int u,v;
        ll w;
        cin>>u>>v>>w;
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }
    const ll INF=numeric_limits<ll>::max()/4;
    vector<array<ll,2>>dist(n+1,{INF,INF});
    using State=tuple<ll,int,int>; // distance, vertex, coupon already used?
    priority_queue<State,vector<State>,greater<State>>pq;
    dist[s][0]=0;
    pq.push({0,s,0});
    while(!pq.empty()){
        auto[d,v,used]=pq.top();
        pq.pop();
        if(d!=dist[v][used]){
            continue; // Check the full state.
        }
        for(auto[u,w]:graph[v]){
            if(d+w<dist[u][used]){
                dist[u][used]=d+w;
                pq.push({d+w,u,used});
            }
            if(!used&&d+w/2<dist[u][1]){
                dist[u][1]=d+w/2;
                pq.push({d+w/2,u,1});
            }
        }
    }
    ll answer=min(dist[t][0],dist[t][1]); // At most one coupon, not exactly one.
    cout<<(answer==INF?-1:answer)<<'\n';
}

Complexity analysis

Expanded V′=2V and E′=O(E). With this lazy priority queue, O((V+E) log(V+E)) time is a safe bound, commonly O((V+E) log V) for simple graphs; O(V+E) memory includes input adjacency and queued states. More generally k states per vertex multiply storage and transitions accordingly. n≤2×10^5, m≤2×10^5, 0≤w≤10^12 keep relevant path totals within long long.

Example input and output

Read n m s t and m undirected edges u v w with nonnegative integer weights. Use at most one coupon replacing w by floor(w/2). Print the minimum cost or −1 if unreachable.

Input

4 4 1 4
1 2 8
2 4 8
1 3 3
3 4 20

Output

12

Travel 1→2→4 and discount either weight-8 edge: 4+8=12, beating the discounted alternative cost 13.

Practical applications

Use when resources, parity, collected keys or action counts affect future transitions. Choose BFS instead if all expanded edges cost one, and 0–1 BFS if they cost only zero or one. A large bitmask can create exponentially many states, so estimate the expanded graph before selecting this technique.

Check your understanding

Why must coupon-used and coupon-unused distances be separate?

Put it into practice

Generalize to at most k discounted traversals.