本人妹子,WA on #2 求助嘤嘤嘤
查看原帖
本人妹子,WA on #2 求助嘤嘤嘤
104292
YellowBean_Elsa楼主2022/12/25 21:09
//coder: Feliks*GM-YB
#include<bits/stdc++.h>
#define fu(i,a,b) for(int i = a, I = (b) + 1; i < I; ++i)
#define fd(i,a,b) for(int i = a, I = (b) - 1; i > I; --i)
#define go(x) for(int i=first[x],y=v[i];i;i=nex[i],y=v[i])
typedef long long ll;
using namespace std;
const int N=2e5+5;

inline int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}int n,m,s,b,f;
int v[N<<1],w[N<<1],nex[N<<1],first[N],tot;
inline void add(int x,int y,int z){
	v[++tot]=y;w[tot]=z;
	nex[tot]=first[x];
	first[x]=tot;
}
bool vis[N];
struct point{
	int t,dis,pre;
	bool operator < (const point &A)const{
		return dis>A.dis;
	}
}p[N];
priority_queue<point> q;
inline void dijk(int st){
	while(q.size())q.pop();
	memset(vis,0,sizeof(vis));
	fu(i,1,n)p[i].dis=(1<<30),p[i].t=i,p[i].pre=-1;
	q.push((point){st,0,-1});p[st].dis=0;
	while(q.size()){
		int x=q.top().t;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		go(x){
			if(p[x].dis+w[i]<p[y].dis){
				p[y].dis=p[x].dis+w[i];
				p[y].pre=x;
				if(!vis[y])q.push(p[y]);
			}if(p[x].dis+w[i]==p[y].dis && x<p[y].pre)p[y].pre=x;
			//¼Ç¼ǰÇý 
		}
	}
}int d1,d2;
int pth[N],cnt,d[N];
int main(){
//	freopen("DATA.in","r",stdin);
//	freopen("WTF.txt","w",stdout);
	n=read(),m=read(),s=read(),b=read(),f=read();
	fu(i,1,m){
		int x=read(),y=read(),z=read();
		add(x,y,z),add(y,x,z);
	}dijk(f);
	d1=p[b].dis,d2=p[s].dis;
	if(2*d1>3*d2){
		puts("YES");
		if(d2%2==0)printf("%d\n",d1-3*d2/2);
		else printf("%d.5\n",d1-(3*d2+1)/2);
	}else{
		puts("NO");
		int pos=s;
		while(pos!=-1){//ѰÕÒСAµÄ·¾¶ 
			pth[++cnt]=pos;
			d[cnt]=d2-p[pos].dis;
			pos=p[pos].pre;
		}dijk(b);//´Ó¹ÖÎï×ö×î¶Ì· 
		int ans=(1<<30);
		fu(i,1,cnt){//go to pth[i] and chase or meet 
			d1=p[pth[i]].dis,d2=d[i];
			if(2*d1>3*d2){//chase
				if(2*(d1-d2)>d[f]-d2)continue;
				ans=min(ans,5*(d1-d2));
			}else{//meet
				ans=min(ans,(d1+d2));
			}
		}
		int r=ans%5;
		if(r==0)printf("%d\n",(ans-r)/5);
		if(r==1)printf("%d.2\n",(ans-r)/5);
		if(r==2)printf("%d.4\n",(ans-r)/5);
		if(r==3)printf("%d.6\n",(ans-r)/5);
		if(r==4)printf("%d.8\n",(ans-r)/5);
	}
	return 0;
}

2022/12/25 21:09
加载中...