/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 4ms 2.348 MiB
#2 Accepted 4ms 2.25 MiB
#3 Accepted 12ms 2.25 MiB
#4 Accepted 8ms 2.367 MiB
#5 Accepted 10ms 2.25 MiB
#6 Accepted 172ms 4.375 MiB
#7 Accepted 173ms 4.5 MiB
#8 Accepted 172ms 4.363 MiB
#9 Accepted 136ms 5.5 MiB
#10 Accepted 235ms 6.227 MiB

代码

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
	char ch=getchar();
	int x=0;
	while(!isdigit(ch))
		ch=getchar();
	while(isdigit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

struct edge
{
	int to,nex,l;
	double p;
}e[200010];
int point[1010],cnt=-1;

inline const void add(int x,int y,int l,double p)
{
	e[++cnt].to=y;
	e[cnt].nex=point[x];
	point[x]=cnt;
	e[cnt].l=l;
	e[cnt].p=p;
}
int n,m; 
int imp[1010],on[200010],Lock[200010];
inline  const int spfa1()
{
	int q[10000],head=1,tail=0;
	int d[1010],vis[1010],i,u,v;
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	q[++tail]=1,vis[1]=1,d[1]=0;
	while(head<=tail)
	{
		u=q[head++];
		vis[u]=0;
		for(i=point[u];i!=-1;i=e[i].nex)
		{
			v=e[i].to;
			if(d[v]>d[u]+e[i].l)
			{		
				imp[v]=i;
				d[v]=d[u]+e[i].l;
				if(!vis[v])
				{
					vis[v]=1;
					q[++tail]=v;
				}
			}
		}
	}
	if(d[n]==d[0])
		return 0;
	return d[n];
}
inline const int spfa2()
{
	int q[10000],head=1,tail=0;
	int d[1010],vis[1010],i,u,v;
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	q[++tail]=1,vis[1]=1,d[1]=0;
	while(head<=tail)
	{
		u=q[head++];
		vis[u]=0;
		for(i=point[u];i!=-1;i=e[i].nex)
		{
			if(Lock[i]) continue;
			v=e[i].to;
			if(d[v]>d[u]+e[i].l)
			{
				d[v]=d[u]+e[i].l;
				if(!vis[v])
				{
					vis[v]=1;
					q[++tail]=v;
				}
			}
		}
	}
	if(d[n]==d[0])
		return 0;
	return d[n];
}

int main()
{
	int i,j,k,l;
	double p;
	memset(point,-1,sizeof(point));
	memset(imp,-1,sizeof(imp));
	n=read(),m=read();
	
	for(i=1;i<=m;i++)
	{
		j=read(),k=read(),l=read(),cin>>p;
		add(j,k,l,p);
		add(k,j,l,p);
	}
	
	int a=spfa1();
	if(a==0)
	{
		cout<<"0.0000000";
		exit(0);
	}
	double tot=0,ans=0;
	cnt=0;
    for(i=2;i<=n;i++)
    	if(imp[i]!=-1)
    	{
    		tot+=e[imp[i]].p;
			on[++cnt]=imp[i];
		}
    ans+=1.0*a*(1-tot);
	for(i=1;i<=cnt;i++)
		if(e[on[i]].p>0)
		{
			Lock[on[i]]=1;Lock[on[i]^1]=1;
            ans+=1.0*spfa2()*e[on[i]].p;
            Lock[on[i]]=0;Lock[on[i]^1]=0;
		}
	printf("%.7lf",ans);	
}

信息

递交者
类型
递交
题目
从中国到阿布拉斯基索沃尔朗特乎斯德麦尔维(原创)
题目数据
下载
语言
C++
递交时间
2017-11-07 11:29:30
评测时间
2017-11-07 11:29:30
评测机
分数
100
总耗时
930ms
峰值内存
6.227 MiB