想拿subtask3和4的分求助
查看原帖
想拿subtask3和4的分求助
664744
_lqs_楼主2022/12/25 18:27
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,m,i,j,ans,k,a,b,c,y,t;
int s,b1,f;
int dis[N],h[N*30],bis[N],qd[N*30],qb[N*30],ud[N],ub[N];
struct AB{
	int a,b,c,n;
}d[N*2];
void cun(int a,int b,int c){
	d[++k].a=a,d[k].b=b,d[k].c=c;
	d[k].n=h[a],h[a]=k;
}
double tis,tib;
signed main(){
	scanf("%d%d%d%d%d",&n,&m,&s,&b1,&f);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		cun(a,b,c);
		cun(b,a,c);
	}
	memset(dis,63,sizeof(dis));
	memset(bis,63,sizeof(bis));
	dis[s]=0,qd[1]=s;
	bis[b1]=0,qb[1]=b1;
	for(y=t=1;y<=t;y++){
		a=qd[y];
		ud[a]=0;
		for(i=h[a];i;i=d[i].n){
			b=d[i].b,c=d[i].c;
			if(dis[b]>dis[a]+c){
				dis[b]=dis[a]+c;
				if(ud[b]==0) ud[b]=1,qd[++t]=b;
			}
		}
	}
	for(y=t=1;y<=t;y++){
		a=qb[y];
		ub[a]=0;
		for(i=h[a];i;i=d[i].n){
			b=d[i].b,c=d[i].c;
			if(bis[b]>bis[a]+c){
				bis[b]=bis[a]+c;
				if(ub[b]==0) ub[b]=1,qb[++t]=b;
			}
		}
	}
	tis=(double)dis[f]/(double)2;
	tib=(double)bis[f]/(double)3;
	if(bis[f]<=dis[f]){
		printf("NO\n");
		printf("%g",(double)dis[f]/5.0);
		return 0;
	}
	if(tis<tib) printf("YES\n");
	else printf("NO\n");
	if(tis<tib){
		double ap=(double)bis[f]-3*tis;
		printf("%g",ap);
	}
	else{
		double p=bis[f]-dis[f];
		printf("%g",p);
	}
	return 0;
}
/*6 5 4 6 3
1 2 2
2 4 1
4 5 1
5 6 1
1 3 1
*/

赛时想拿这两部分分,结果 subtask 4subtask \ 4过了卡了 33 调了半天也不知道错哪了。

2022/12/25 18:27
加载中...