CF Lane Switching 參考答案
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
?bool can_pass(PII x,PII y,double limit){
? ? int maxf=max(x.first,y.first);
? ? int mins=min(x.second,y.second);
? ? if(mins-maxf-limit>=0){
? ? ? ? return true;
? ? }else{
? ? ? ? return false;
? ? }? ??
}? ??
bool reachLastLane(int start, vector<vector<int>>& net, int n, map<int, pair<int,int> >& v2p){
? ? stack<int> s;
? ? s.push(start);
? ? vector<bool> vis(n);
? ? while(!s.empty()){
? ? ? ? int a=s.top();
? ? ? ? s.pop();
? ? ? ? for(int v:net[a]){
? ? ? ? ? ? if(!vis[v]){
? ? ? ? ? ? ? ? if(v2p[v].first==n-1){
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? vis[v]=true;
? ? ? ? ? ? ? ? ? ? s.push(v);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return false;
}? ??
int main()
{
? ? int n,m,r,acms,acml;
? ? cin>>n>>m>>r;
? ? int lane,len,start ;
? ? cin>>lane>>acml>>acms;
? ? vector< vector< pair<int,int> > > cars(n);
? ? vector< vector< pair<int,int> > > road(n);
? ? vector< vector< int > > p2v(n);
? ? map<int, pair<int,int> > v2p;
? ??
? ? for(int i=1;i<m;i++){
? ? ? ? cin>>lane>>len>>start;
? ? ? ? cars[lane].push_back(make_pair(start,start+len));
? ? }
? ? int vexnum=0;
? ? for(int i=0;i<n;i++){
? ? ? ? sort(cars[i].begin(),cars[i].end());
? ? ? ? int num=cars[i].size();
? ? ? ? if(num>0){
? ? ? ? ? ? road[i].push_back(make_pair(0,cars[i][0].first));
? ? ? ? }else{
? ? ? ? ? ? road[i].push_back(make_pair(0,r));
? ? ? ? }
? ? ? ? p2v[i].push_back(vexnum);
? ? ? ? v2p[vexnum]=make_pair(i,p2v[i].size()-1);
? ? ? ? vexnum++;
? ? ? ? for(int j=1;j<num;j++){
? ? ? ? ? ? road[i].push_back(make_pair(cars[i][j-1].second,cars[i][j].first));
? ? ? ? ? ? p2v[i].push_back(vexnum);
? ? ? ? ? ? v2p[vexnum]=make_pair(i,p2v[i].size()-1);
? ? ? ? ? ? vexnum++;
? ? ? ? }
? ? ? ? if(num>0){
? ? ? ? ? ? road[i].push_back(make_pair(cars[i][num-1].second,r));
? ? ? ? ? ? p2v[i].push_back(vexnum);
? ? ? ? ? ? v2p[vexnum]=make_pair(i,p2v[i].size()-1);
? ? ? ? ? ? vexnum++;
? ? ? ? }? ??
? ? }
? ? //find out start vex
? ? int startv;
? ? auto ip=upper_bound(road[0].begin(),road[0].end(),make_pair(acms,acms+r+1));
? ? ip--;
? ? int index=ip-road[0].begin();
? ? startv=p2v[0][index];
? ? ? ??
? ? double lf=-(double)acml/2, rt=((double)r+1)/2;
? ? while(rt-lf>1e-6){
? ? ? ? vector<vector<int>> net(vexnum);
? ? ? ? double md=(lf+rt)/2;
? ? ? ? double limit=2*md+acml;
? ? ? ? //construct net
? ? ? ? for(int i=0;i<n-1;i++){
? ? ? ? ? ? int k=0,l=0;
? ? ? ? ? ? while(k<road[i].size() && l<road[i+1].size()){
? ? ? ? ? ? ? ? if(can_pass(road[i][k],road[i+1][l],limit)){
? ? ? ? ? ? ? ? ? ? net[p2v[i][k]].push_back(p2v[i+1][l]);
? ? ? ? ? ? ? ? ? ? net[p2v[i+1][l]].push_back(p2v[i][k]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(road[i][k].second>road[i+1][l].second){
? ? ? ? ? ? ? ? ? ? l++;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? k++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }? ??
? ? ? ? if(reachLastLane(startv, net, n, v2p)){
? ? ? ? ? ? lf=md;
? ? ? ? }else{
? ? ? ? ? ? rt=md;
? ? ? ? }
? ? }
? ? if(lf>=0){
? ? ? ? printf("%.5f\n",lf);
? ? }else{
? ? ? ? cout<<"Impossible"<<endl;
? ? }? ??
? ? return 0;
}
