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;
}
