萌新爆0求助
查看原帖
萌新爆0求助
743048
ran_qwq楼主2022/12/25 18:17
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10,INF=1e9;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
void Write(int x)
{
	if(x<0)
	{
		putchar('-'),Write(-x);
		return;
	}
	if(x<10)
	{
		putchar(x+'0');
		return;
	}
	Write(x/10),putchar(x%10+'0');
}
void write(int x,char *s)
{
	Write(x),printf("%s",s);
}
int n,m,S,B,F;
int id,to[N],head[N],ne[N],w[N];
int dis[N][2],vis[N][2],pre[N];
void add(int x,int y,int z)
{
	to[++id]=y,w[id]=z,ne[id]=head[x],head[x]=id;
}
void spfa(int s,int p)
{
	queue<int> q;q.push(s);
	for(int i=1;i<=n;i++)
		dis[i][p]=0x3f,vis[i][p]=0;
	dis[s][p]=0,vis[s][p]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop(),vis[u][p]=0;
		for(int i=head[u];i;i=ne[i])
		{
			int v=to[i];
			if(dis[u][p]+w[i]<dis[v][p])
			{
				dis[v][p]=dis[u][p]+w[i];
				if(!vis[v][p])
				{
					
					vis[v][p]=1,q.push(v);
					if(p)
						pre[v]=u;
				}
			}
		}
	}
}
void print(double x)
{
	double xx=x;int y=x;
	if(x==y)
		printf("%.0lf",x);
	else
	{
		xx*=10,y=xx;
		if(xx==y)
			printf("%.1lf",x);
		else
			printf("%.2lf",x);
	}
}
signed main()
{
	n=read(),m=read(),S=read(),B=read(),F=read();
	while(m--)
	{
		int x=read(),y=read(),z=read();
		add(x,y,z),add(y,x,z);
	}
	spfa(B,0),spfa(S,1);
	for(int i=F;pre[i];i=pre[i])
		if(dis[i][1]/2.0>=dis[i][0]/3.0)
			puts("NO"),print(dis[i][1]/2.0),exit(0);
	puts("YES"),print((dis[F][0]/3.0-dis[F][1]/2.0)*3);
}

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