30pts代码求调
查看原帖
30pts代码求调
932094
caoruiqi楼主2024/2/24 16:45

#25WA wrong answer Too long on line 2.

//#pragma GCC optimize(3,"Ofast","inline")
//https://www.mayiwsk.com/78_78181/33887035.html
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
void write(long long x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
	return;
}
int n,m,s,b,f,head[200001],tmp,sum,i,u,a,v,pre[200001],fa[200001];
long long dis[200001],dis1[200001],dis2[200001],x;
double ans;
bitset<200001>pd,pd1,pd2;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
struct node{
	int nxt,to,num;
};
node e[400001];
void add(int a,int b,int c){
	e[++sum].num=c;
	e[sum].to=b;
	e[sum].nxt=head[a];
	head[a]=sum;
}
int main(){
	//freopen("data7.in","r",stdin);
	//freopen(".out","w",stdout);
	memset(dis,0x7f,sizeof(dis));
	memset(dis1,0x7f,sizeof(dis1));
	memset(dis2,0x7f,sizeof(dis2));
	n=read();
	m=read();
	s=read();
	b=read();
	f=read();
	for(i=1;i<=m;i++){
		u=read();
		v=read();
		a=read();
		add(u,v,a);
		add(v,u,a);
	}
	dis[f]=0;
	q.push(make_pair(dis[f],f));
	while(!q.empty()){
		tmp=q.top().second;
		q.pop();
		if(pd[tmp]){
			continue;
		}
		pd[tmp]=true;
		for(i=head[tmp];i!=0;i=e[i].nxt){
			if(dis[e[i].to]>dis[tmp]+e[i].num){
				pre[e[i].to]=tmp;
				dis[e[i].to]=dis[tmp]+e[i].num;
				q.push(make_pair(dis[e[i].to],e[i].to));
			}
		}
	}
	dis1[s]=0;
	q.push(make_pair(dis1[s],s));
	while(!q.empty()){
		tmp=q.top().second;
		q.pop();
		if(pd1[tmp]){
			continue;
		}
		pd1[tmp]=true;
		for(i=head[tmp];i!=0;i=e[i].nxt){
			if(dis1[e[i].to]>dis1[tmp]+e[i].num){
				dis1[e[i].to]=dis1[tmp]+e[i].num;
				q.push(make_pair(dis1[e[i].to],e[i].to));
			}
		}
	}
	dis2[b]=0;
	q.push(make_pair(dis2[b],b));
	while(!q.empty()){
		tmp=q.top().second;
		q.pop();
		if(pd2[tmp]){
			continue;
		}
		pd2[tmp]=true;
		for(i=head[tmp];i!=0;i=e[i].nxt){
			if(dis2[e[i].to]>dis2[tmp]+e[i].num){
				dis2[e[i].to]=dis2[tmp]+e[i].num;
				q.push(make_pair(dis2[e[i].to],e[i].to));
			}
		}
	}
	for(i=s;i!=0;i=pre[i]){
		fa[pre[i]]=i;
	}
	for(i=s;i!=0;i=pre[i]){
		if(dis1[i]*3>=dis2[i]*2){
			printf("NO\n");
			ans=min((dis1[i]+dis2[i])/5.0,(dis2[fa[i]]-dis1[fa[i]])/1.0);
			x=(ans+0.001)*100;
			if(x%100==0){
				write(x/100);
			}
			else if(x%10==0){
				printf("%.1lf",0.01*x);
			}
			else{
				printf("%.2lf",0.01*x);
			}
			return 0;
		}
	}
	printf("YES\n");
	ans=dis2[f]-dis1[f]*3.0/2.0;
	x=(ans+0.001)*100;
	if(x%100==0){
		write(x/100);
	}
	else if(x%10==0){
		printf("%.1lf",0.01*x);
	}
	else{
		printf("%.2lf",0.01*x);
	}
	return 0;
}
/*
10 12 1 8 6
1 2 1
2 3 4
3 4 7
4 5 5
5 7 8
4 7 2
1 7 11
9 10 1
9 8 4
2 9 8
7 6 1
1 3 2
 */
2024/2/24 16:45
加载中...