为什么#9有精度丢失
查看原帖
为什么#9有精度丢失
286116
Robert08楼主2021/12/26 15:19
#include<bits/stdc++.h>
using namespace std;
double dist[2000];
int head[2000],go[2000],n,m,st,fi;
struct road{
	int s,f;
	double val;
} a[200000];
bool cmp(road a,road b){
	return a.s<b.s;
}
double dt(int x1,int y1,int x2,int y2){
	double dis;
	dis=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
//	printf("%d %d %.2f",(x1-x2)*(x1-x2),(y1-y2)*(y1-y2),dis);
	return dis;
} ;
void rst(){
	for(int i=0;i<n;i++)	dist[i]=1;
	return;
}
void spfa(){
	queue<int> q;
	rst();
	dist[st-1]=0;
	q.push(st-1);
	go[st-1]=1;
	while(!q.empty()){
		if(head[q.front()]==-1){
			q.pop();
			continue;
		}	
//		printf("Scan road started with %d:\n",q.front()+1);
		int h=head[q.front()];
		int ed=m-1;
		for(int i=q.front()+1;i<n;i++){
			if(head[i]!=-1){
				ed=head[i];	
//				printf("ed:%d i:%d\n",ed,i);
				break;
			}	
		}
//		printf("---Scan roads num %d to num %d\n",h,ed-1);
		while(h<ed){
//			printf("----Road %d to %d is ",a[h].s,a[h].f);
			if(dist[a[h].f-1]>a[h].val+(1-a[h].val)*dist[a[h].s-1]){
//				printf("changed from %d to %d\n",dist[a[h].f-1],a[h].val+dist[a[h].s-1]);
				dist[a[h].f-1]=a[h].val+(1-a[h].val)*dist[a[h].s-1];
				if(go[a[h].f-1]==0){
					q.push(a[h].f-1);
					go[a[h].f-1]=1;
				}	
			}	
//			else	printf("normal\n");
			h++;
		}
		go[q.front()]=0;
//		printf("Pop %d\n\n",q.front());
		q.pop();
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m*2;i+=2){
		scanf("%d%d%lf",&a[i].s,&a[i].f,&a[i].val);
		a[i].val/=100;
		a[i+1].s=a[i].f;a[i+1].f=a[i].s;a[i+1].val=a[i].val;
	} 
	scanf("%d%d",&st,&fi);
	sort(a,a+m*2,cmp);
	memset(head,-1,sizeof(head));
	for(int i=0;i<m*2;i++){
		if(head[a[i].s-1]==-1)	head[a[i].s-1]=i;
	}
	spfa();
	printf("%.8f",100/(1-dist[fi-1]));
	return 0;
} 
2021/12/26 15:19
加载中...