Untitled
unknown
plain_text
a year ago
4.2 kB
1
Indexable
Never
#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; }