/ Randle /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Accepted 5ms 4.594 MiB
#2 Wrong Answer 7ms 4.5 MiB
#3 Wrong Answer 16ms 4.598 MiB
#4 Wrong Answer 7ms 4.5 MiB
#5 Wrong Answer 9ms 4.617 MiB
#6 Wrong Answer 91ms 5.469 MiB
#7 Wrong Answer 106ms 5.465 MiB
#8 Wrong Answer 125ms 4.949 MiB
#9 Wrong Answer 64ms 4.125 MiB
#10 Wrong Answer 92ms 5.48 MiB

代码

#include<bits/stdc++.h>
inline void read(int&a)
{
	a=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
inline void write(int a)
{
	if(a<0){putchar('-');a=-a;}
	if(a>9)write(a/10);
	putchar(a%10+'0');
}
#define smaxn 200001
#define pmaxn 1001
int n,m,d=-1;
int point[pmaxn],on_chain[pmaxn],next[smaxn],to[smaxn],len[smaxn];
double p[smaxn];
double ans=0.0;
inline void add(int a,int b,int c,double e)
{
	next[++d]=point[a];
	to[d]=b;
	len[d]=c;
	point[a]=d;
	p[d]=e;
}
int prior[pmaxn],dis[pmaxn];
int que[500000],start,end;
bool in_que[pmaxn],exist[smaxn];
inline int spfa()
{
	start=0;end=-1;
	memset(in_que,false,sizeof(in_que));
	memset(dis,0x7f,sizeof(dis));
	dis[1]=0;in_que[1]=true;que[++end]=1;
	while(end>=start)
	{
		int p=que[start],side=point[p];
		while(side!=-1)
		{
			if(exist[side]&&dis[to[side]]>dis[p]+len[to[side]])
			{
				prior[to[side]]=side;
				dis[to[side]]=dis[p]+len[side];
				if(!in_que[to[side]])
				{
					que[++end]=to[side];
					in_que[to[side]]=true;
				}
			}
			side=next[side];
		}
		in_que[p]=false;
		++start;
	}
	if(dis[n]<dis[0])return dis[n];
	else return 0;
}
int main()
{
	memset(in_que,false,sizeof(in_que));
	memset(point,-1,sizeof(point));
	read(n);read(m);
	int u,v,l;
	double pi;
	for(int i=1;i<=m;i++)
	{
		read(u);read(v);read(l);scanf("%lf",&pi);
		add(u,v,l,pi);add(v,u,l,pi);
	}
	memset(on_chain,-1,sizeof(on_chain));
	memset(exist,true,sizeof(exist));
	int k=spfa(),q=0;
	double del=0;
	for(int i=2;i<=n;i++){del+=p[prior[i]];on_chain[++q]=prior[i];}
	ans+=(double)(k)*(1-del);
	for(int i=1;i<=q;i++)
	{
		if(p[on_chain[i]]>0&&on_chain[i]>-1)
		{
			exist[on_chain[i]]=false;exist[on_chain[i]^1]=false;
			ans+=(double)(spfa())*p[on_chain[i]];
			exist[on_chain[i]]=true;exist[on_chain[i]^1]=true;
		}
	}
	printf("%.7lf",ans);
	return 0;
}       

信息

递交者
类型
递交
题目
从中国到阿布拉斯基索沃尔朗特乎斯德麦尔维(原创)
题目数据
下载
语言
C++
递交时间
2017-11-06 17:09:20
评测时间
2017-11-06 20:49:23
评测机
分数
10
总耗时
525ms
峰值内存
5.48 MiB