Untitled

#include <queue>
#include <algorithm>
  
  
using namespace ::std;
  
  
const int MAX_STATION = 40000;
const int MAX_LINE = 5;
const int INF = 1000000000;
  
  
int n;
  
  
bool isActive[MAX_STATION][MAX_LINE];
int prevStation[MAX_STATION][MAX_LINE];
int nextStation[MAX_STATION][MAX_LINE];
  
  
bool canTransfer[MAX_LINE][MAX_LINE];
  
  
void init(int N, int mLastStation1[5], int mLastStation2[5])
{
    n = N;
  
  
    for (int i = 0; i < n; i++)
        for (int j = 0; j < MAX_LINE; j++)
            isActive[i][j] = false;
  
  
    for (int i = 0; i < MAX_LINE; i++)
        for (int j = 0; j < MAX_LINE; j++)
            canTransfer[i][j] = (i == j);
  
  
    for (int i = 0; i < MAX_LINE; i++)
    {
        isActive[mLastStation1[i]][i] = true;
        prevStation[mLastStation1[i]][i] = INF;
        nextStation[mLastStation1[i]][i] = mLastStation2[i];
  
  
        isActive[mLastStation2[i]][i] = true;
        prevStation[mLastStation2[i]][i] = mLastStation1[i];
        nextStation[mLastStation2[i]][i] = INF;
  
  
        for (int j = 0; j < MAX_LINE; j++)
            if (isActive[mLastStation1[i]][j] || isActive[mLastStation2[i]][j])
                canTransfer[i][j] = canTransfer[j][i] = true;
    }
}
  
  
void add(int mLine, int mPrevStation, int mStation)
{
    int mNextStation = nextStation[mPrevStation][mLine];
  
  
    isActive[mStation][mLine] = true;
    nextStation[mPrevStation][mLine] = mStation;
    prevStation[mStation][mLine] = mPrevStation;
    nextStation[mStation][mLine] = mNextStation;
    prevStation[mNextStation][mLine] = mStation;
  
  
    for (int i = 0; i < MAX_LINE; i++)
        if (isActive[mStation][i])
            canTransfer[mLine][i] = canTransfer[i][mLine] = true;
}
  
  
int travelTime[MAX_STATION][MAX_LINE];
queue<pair<int, int>> travelTimeQ;
  
  
int minTravelTime(int mStartStation, int mEndStation)
{
    travelTimeQ = {};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < MAX_LINE; j++)
            travelTime[i][j] = INF;
  
  
    for (int i = 0; i < MAX_LINE; i++)
    {
        if (isActive[mStartStation][i])
        {
            travelTimeQ.push({mStartStation, i});
            travelTime[mStartStation][i] = 0;
        }
    }
  
  
    while (!travelTimeQ.empty())
    {
        int station = travelTimeQ.front().first;
        int line = travelTimeQ.front().second;
        int nowTravelTime = travelTime[station][line];
  
        if(station == mEndStation)return nowTravelTime;
  
        for (auto i : {prevStation[station][line], nextStation[station][line]})
        {
            if (i != INF && travelTime[i][line] == INF)
            {
                travelTimeQ.push({i, line});
                travelTime[i][line] = nowTravelTime + 1;
            }
        }
  
  
        for (int i = 0; i < MAX_LINE; i++)
        {
            if (isActive[station][i] && travelTime[station][i] == INF)
            {
                travelTimeQ.push({station, i});
                travelTime[station][i] = nowTravelTime + 1;
            }
        }
        travelTimeQ.pop();
    }
  
    return -1;
}
  
  
int transfer[MAX_LINE];
queue<int> transferQ;
  
  
int minTransfer(int mStartStation, int mEndStation)
{
    transferQ = {};
    for (int i = 0; i < MAX_LINE; i++)
        transfer[i] = INF;
  
  
    for (int i = 0; i < MAX_LINE; i++)
    {
        if (isActive[mStartStation][i])
        {
            transferQ.push(i);
            transfer[i] = 0;
        }
    }
  
  
    while (!transferQ.empty())
    {
        int line = transferQ.front();
        int nowTransfer = transfer[line];
        for(int i=0; i<5; i++)
        {
            if(isActive[mEndStation][i] && i == line)return nowTransfer;
        }
        for (int i = 0; i < MAX_LINE; i++)
        {
            if (canTransfer[line][i] && transfer[i] == INF)
            {
                transferQ.push(i);
                transfer[i] = nowTransfer + 1;
            }
        }
        transferQ.pop();
    }
 
    return -1;
}