Please read the problem description:
The problem is BFS question. If you want to get full marks, you should read the problem carefully. must understand:
Walk to Nth station
Each day only has one train running from the first station to the Nth station. you must understand "one". This is very important, this means if you can not do train->walk->train, because you need to wait for the train coming that only one train.
The solution should be:
Do BFS to get the distance that each station walks to the Nth station.
Each station m (position) to Nth station minimum distance is:
min(take train route, train + walk)
3. Make an ordered set to store all minimum distances to the Nth station.
4. Each day, swap two stations, and update the ordered set, the 0 elements of
the set is one answer.
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
vector<int> fixedRoute[200001];
int valueToPos[200001];
int position[200001];
int dis[200001];
bool visited[200001];
int wdist[200001];
int N, W, D;
void bfs(int n){
bool vis[n+1];
memset(vis, 0, sizeof(vis));
vis[n] = true; // Start at statio N
wdist[n] = 0;
queue<int> q;
q.push(n);
while(!q.empty()){
int cur_station = q.front();
q.pop();
for( int i = 0; i < fixedRoute[cur_station].size(); i++)
{
if(!vis[fixedRoute[cur_station][i]]){
wdist[fixedRoute[cur_station][i]] = wdist[cur_station] + 1;
vis[fixedRoute[cur_station][i]] = true;
q.push(fixedRoute[cur_station][i]);
}
}
}
}
int main() {
cin >> N;
cin >> W;
cin >> D;
for(int i = 0; i < W; i++){
int m ,n;
cin >> m;
cin >> n;
fixedRoute[n].push_back(m);
}
memset(wdist, 200002, 200001*sizeof(int));
bfs(N);
int subwayline[N+1]; // subwayline[0] is unused, subwayline[1] to subwayline[n] stores the station number at that point
multiset<int> culdist; // culmitive distance... doesn't matter which station it's from / to all we care about is what the distance is and a multimap is perfect for this.
for(int a=1;a<=N;++a){
cin >> subwayline[a];
// Subway distance is = index of subwayline -1
culdist.insert(a-1 + wdist[subwayline[a]]);
// Distance on train + walking distance
}
// For each "station swap"
for(int i=0;i<D;++i){
int station1, station2;
cin >> station1 >> station2; // Gives station location
// Get old distance and remove from multiset
int station1OldDist = station1-1 + wdist[subwayline[station1]];
int station2OldDist = station2-1 + wdist[subwayline[station2]];
culdist.erase(culdist.find(station1OldDist));
culdist.erase(culdist.find(station2OldDist));
// Swap opreration
swap(subwayline[station1], subwayline[station2]);
// Add new distances
culdist.insert(station1-1 + wdist[subwayline[station1]]);
culdist.insert(station2-1 + wdist[subwayline[station2]]);
// Output the minimum distance - multisets are dynamically sorted internally
}
return 0;
}
Comments