reserved bus

#include<bits/stdc++.h>
using namespace std;
 
vector<pair<int,int>> adj[550];
int ans = INT_MAX;
int dist[505][505];
vector<vector<int>> permutations;
int totalNode;
 
void init(int N, int K, int mRoadAs[], int mRoadBs[], int mLens[])
{
    totalNode = N;
    for (int i = 1; i <= N; i++) {
        adj[i].clear();
    }
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < K; i++) {
        adj[mRoadAs[i]].push_back({ mLens[i], mRoadBs[i] });
        adj[mRoadBs[i]].push_back({ mLens[i], mRoadAs[i]});
    }
     
}
 
void addRoad(int mRoadA, int mRoadB, int mLen)
{
    adj[mRoadA].push_back({ mLen, mRoadB });
    adj[mRoadB].push_back({ mLen, mRoadA });
}
 
void dijkstra(int node, int start, int end) {
 
    for (int i = 0; i <= totalNode; i++)
    {
        dist[node][i] = 100000001;
    }
 
    dist[node][node] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; 
    pq.push({ 0, node });
    while (!pq.empty()) {
        int n = pq.top().second;
        pq.pop();
 
        if (n == start || n == end) {
            continue;
        }
        for (auto pr : adj[n]) {
            if ((dist[node][n] + pr.first) < dist[node][pr.second]) {
                dist[node][pr.second] = dist[node][n] + pr.first;
                pq.push({ dist[node][pr.second], pr.second });
            }
        }
    }
}
 
int findPath(int mStart, int mEnd, int M, int mStops[])
{
    int ans = 100000001;
    sort(mStops, mStops + M);
    for (int i = 0; i < M; i++)
        dijkstra(mStops[i], mStart, mEnd);
    do {
        int currDist = dist[mStops[0]][mStart];
        for (int i = 1; i < M; i++)
            currDist += dist[mStops[i - 1]][mStops[i]];
        currDist += dist[mStops[M - 1]][mEnd];
        ans = min(ans, currDist);
    } while (next_permutation(mStops, mStops + M));
    return ans == 100000001 ? -1 : ans;
}

#include<map>
#include<queue>
#include<unordered_map>
using namespace std;
#define MAX_N 500+5
#define HEAPSIZE 500
  
map<int, int> stationMap[MAX_N];
map<int, int> needstationMap[MAX_N];
  
  
struct queue_data
{
    int id;
    int cost;
    int havepass;
};
  
int findPathMin = 100000;
int stationNum = 0;
int dist[MAX_N];
int visit[MAX_N];
int visitCnt = 1;
int find_min_len(int start, int end, int flag, int no_index1, int no_index2)
{
    if (start == end) return 0;
  
    queue<pair<int, int>> q;
  
    for (int i = 1; i <= stationNum; i++)
    {
        dist[i] = 0x7fffffff;
    }
    dist[start] = 0;
  
    q.push({ start,0 });//id - len
  
    while (q.size() != 0)
    {
        auto tmp = q.front();
        q.pop();
  
        for (auto it : stationMap[tmp.first])
        {
            int next_id = it.first;
            int next_len = it.second + tmp.second;
  
            if (next_len >= dist[next_id]) continue;
  
            if (flag == 1)
            {
                if (next_id == no_index1 || next_id == no_index2)
                {
                    continue;
                }
            }
  
            dist[next_id] = next_len;
            q.push({ next_id,next_len });
        }
    }
  
    return dist[end];
}
  
void init(int N, int K, int mRoadAs[], int mRoadBs[], int mLens[])
{
    stationNum = N;
    for (int i = 1; i <= N; i++)
    {
        stationMap[i].clear();
    }
  
    for (int i = 0; i < K; i++)
    {
        int from_id = mRoadAs[i];
        int to_id = mRoadBs[i];
        int len = mLens[i];
        stationMap[from_id].emplace(to_id, len);
        stationMap[to_id].emplace(from_id, len);
    }
}
  
void addRoad(int mRoadA, int mRoadB, int mLen)
{
    stationMap[mRoadA].emplace(mRoadB, mLen);
    stationMap[mRoadB].emplace(mRoadA, mLen);
}
  
void make_map(int mStart, int mEnd, int M, int mStops[])
{
    for (int i = 0; i < MAX_N; i++)
    {
        needstationMap[i].clear();
    }
  
  
    for (int i = 0; i < M; i++)
    {
        int min_len_1 = find_min_len(mStart, mStops[i], 1, mEnd, -1);
        needstationMap[mStart].emplace(mStops[i], min_len_1);
        needstationMap[mStops[i]].emplace(mStart, min_len_1);
  
        int min_len_2 = find_min_len(mEnd, mStops[i], 1, mStart, -1);
        needstationMap[mEnd].emplace(mStops[i], min_len_2);
        needstationMap[mStops[i]].emplace(mEnd, min_len_2);
    }
  
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (mStops[i] != mStops[j])
            {
                int min_len = find_min_len(mStops[i], mStops[j], 1, mStart, mEnd);
                needstationMap[mStops[i]].emplace(mStops[j], min_len);
                needstationMap[mStops[j]].emplace(mStops[i], min_len);
  
            }
        }
    }
  
}
  
void dfs(int id,int cost,int min,int start,int end,int havepass,int M)
{
  
    if (visit[id]== visitCnt || (id == end && havepass < M) || cost > findPathMin)
        return;
  
    if (id != start && id != end)
        havepass += 1;
  
    if (id == end)
    {
        if (havepass >= M)
        {
            findPathMin = cost < findPathMin ? cost : findPathMin;
            return;
        }
        else
            return;
    }
  
    visit[id] = visitCnt;
    for (auto per: needstationMap[id])
    {
        if (per.second==0x7fffffff)
            continue;
        int flag = 0;
        int next_id = per.first;
        int next_cost = per.second + cost;
        dfs(next_id, next_cost, min, start, end, havepass,M);
    }
    visit[id] = 0;
    if (id != start && id != end)
        havepass -= 1;
}
  
  
int findPath(int mStart, int mEnd, int M, int mStops[])
{
    visitCnt++;
    make_map(mStart, mEnd, M, mStops);
    findPathMin = 100000;
    dfs(mStart, 0, findPathMin, mStart, mEnd, 0, M);
    findPathMin = findPathMin == 100000 ? -1 : findPathMin;
    return findPathMin;
}