【21 ZR联赛集训 day10】不知道高到哪里去了
二分答案。设敌人的速度是 \(1\),二分我的速度 \(v\),我可以从 \(C\) 走到 \(T\) 当对于每个我到达的点 \(u\),敌人无法比我先到达,即敌人到达 \(u\) 最短用时比我大。
先求敌人到每个结点的最短路,然后对于二分的一个 \(v\),从 \(C\) 开始搜,我到一个点的最短用时小于敌人到这个点的最短用时时,我可以到达这个点,维护 \(C\) 出发最短路即可(\(t=\frac{s}{v}\))。如果我可以到达 \(T\) 返回 \(true\)。
Code
#include<bits/stdc++.h>
#define pf printf
#define sf scanf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define isdigit(x) (x>='0'&&x<='9')
//#define int ll
using namespace std;
typedef long long ll;
const int N=1e4+7,M=5e5+7,inf=0x7f7f7f7f;
template <typename T>
void read(T &sum){
sum=0;
T fl=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) (ch=='-')&&(fl=-1);
for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-'0';
sum=sum*fl;
}
template <typename T>
void write(T x){
static int st[36];
int top=0;
if(x<0) putchar('-'),x=-x;
do{
st[top++]=x%10,x/=10;
}while(x);
while(top) putchar(st[--top]+'0');
}
template <typename T>
void write(T x,char ch){
write(x);
putchar(ch);
}
int head[N],cnt;
struct edge{
int to,val,ne;
}e[M<<1];
void addedge(int u,int v,int w){
e[++cnt]={v,w,head[u]};head[u]=cnt;
}
map<pair<int,int>,int> mp;
vector<pair<int,int> > vec;
int n,m;
int u,v,w;
int S,A,T;
int dis[2][N],vi[N];
struct qst{
int x,d;
bool operator <(const qst b)const{
return d>b.d;
}
};
void getdis(int rt,int op=0){
// pf("getdis(%d)\n",rt);
memset(dis[op],0x7f,sizeof(dis[op]));
memset(vi,0,sizeof(vi));
priority_queue<qst> que;
dis[op][rt]=0;
que.push({rt,0});
while(!que.empty()){
qst k=que.top();
que.pop();
int u=k.x,d=k.d;
if(vi[u]) continue;
// pf("%d %d\n",u,d);
vi[u]=1;
for(int i=head[u];i;i=e[i].ne){
int v=e[i].to,w=e[i].val;
if(d+w<dis[op][v]){
dis[op][v]=d+w;
que.push({v,dis[op][v]});
}
}
}
}
bool dfs(int rt,double vv,int op=1){
memset(dis[op],0x7f,sizeof(dis[op]));
memset(vi,0,sizeof(vi));
priority_queue<qst> que;
dis[op][rt]=0;
que.push({rt,0});
while(!que.empty()){
qst k=que.top();
que.pop();
int u=k.x,d=k.d;
if(vi[u]) continue;
if(1.0*dis[1][u]/vv>=1.0*dis[0][u]) {dis[1][u]=inf;continue; }
// pf("%d %d\n",u,d);
vi[u]=1;
for(int i=head[u];i;i=e[i].ne){
int v=e[i].to,w=e[i].val;
if(d+w<dis[op][v]){
dis[op][v]=d+w;
que.push({v,dis[op][v]});
}
}
}
return dis[op][T]!=inf;
}
bool check(double v){
return dfs(S,v);
}
int main(){
// freopen("test.out","w",stdout);
read(n),read(m);
rep(i,1,m){
read(u),read(v),read(w);
if(u==v) continue;
vec.push_back({u,v});
if(mp.find({u,v})==mp.end()) mp[{u,v}]=mp[{v,u}]=w;
else mp[{u,v}]=mp[{v,u}]=min(mp[{u,v}],w);
}
for(pair<int,int> ei:vec){
if(mp[ei]) {
addedge(ei.first,ei.second,mp[ei]);
addedge(ei.second,ei.first,mp[ei]);
mp[ei]=0;
}
}
read(S),read(A),read(T);
if(S==A){
pf("-1\n");return 0;
}
if(S==T){
pf("0.00000\n");return 0;
}
getdis(A,0);
// pf("%lld\n",dis[0][3]);
// getdis(S,1);
double l=0,r=100*N;
while(l<r-0.00001){
double mid=(l+r)/2;
// pf("mid %.6lf\n",mid);
if(check(mid)) r=mid;
else l=mid;
}
if(r==100*N) pf("-1\n");
else pf("%.5lf\n",r);
}
没有回复内容