Expert.
Put your skills to the test.

Problem summary

An undirected network has bus and airplane edges. Find the fewest vehicles needed from city 1 to city N while using at most K airplanes.

Constraints

2 ≤ N ≤ 200000; 1 ≤ M ≤ 3N; 1 ≤ K ≤ 2.

Worked example

Official statement example.

5 5 1
1 2 1
2 3 1
3 5 2
2 4 1
4 5 2

3

Solution analysis

1. A city alone is insufficient to describe a search state: arriving with no flights used can enable a continuation unavailable after spending the budget. Use states (city, flights used), with K+1 layers.
2. A bus keeps the layer, and an airplane increases it by one if the budget allows. Every transition uses exactly one vehicle, so ordinary BFS from (1,0) finds shortest distances in this expanded graph.
3. In the example BFS can follow 1→2→3→5, reaching (5,1) in three transitions. The result is the minimum distance to city N in any permitted layer; unreachable layers are ignored.

Why it works

Each permitted route corresponds to an expanded-graph walk with the same number of edges, and every expanded walk represents a permitted route. BFS finds shortest walks in an unweighted graph, and minimizing over final layers therefore gives exactly the required answer.

Watch out. Do not mark a city visited globally; different flight counts are different states.

An independently written complete program with standard headers.

// Key idea: Each permitted route corresponds to an expanded-graph walk with the same number of edges,
// and every expanded walk represents a permitted route. BFS finds shortest walks in an unweighted
// graph, and minimizing over final layers therefore gives exactly the required answer.
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<pair<int,int>>>graph(n);
    for(int i=0;i<m;++i){
        int a,b,type;
        cin>>a>>b>>type;
        --a;
        --b;
        graph[a].push_back({b,type-1});
        graph[b].push_back({a,type-1});
    }
    vector<vector<int>>distance(n,vector<int>(k+1,-1));
    queue<pair<int,int>>pending;
    distance[0][0]=0;
    pending.push({0,0});
    while(!pending.empty()){
        auto[u,used]=pending.front();
        pending.pop();
        for(auto[v,flight]:graph[u]){
            int next=used+flight;
            if(next<=k&&distance[v][next]==-1){
                distance[v][next]=distance[u][used]+1;
                pending.push({v,next});
            }
        }
    }
    int answer=-1;
    for(int value:distance[n-1]){
        if(value!=-1&&(answer==-1||value<answer)){
            answer=value;
        }
    }
    cout<<answer<<'\n';
}