求调WAon#2#8
查看原帖
求调WAon#2#8
386892
REMAC楼主2022/12/26 16:08
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;

using Pii=pair<int,int>;

struct Edge {
	int v,w;
};

vector<Edge> g[maxn];
int fromS[maxn], toT[maxn], fromB[maxn];
bool vis[maxn];

void dij(int s,int *dis) {
	memset(dis,0x3f,200009*sizeof(int));
	dis[s]=0;
	priority_queue<Pii,vector<Pii>,greater<>> que;
	que.push(Pii {0,s});
	while(!que.empty()) {
		int u=que.top().second;
		que.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(Edge e:g[u]) {
			int v=e.v;
			if(dis[v]>dis[u]+e.w) {
				dis[v]=dis[u]+e.w;
				que.push(Pii {dis[v],v});
			}
		}
	}
	memset(vis,0,sizeof vis);
}

int gp(double a)
{
	if(floor(a)==a) return 0;
	if(floor(a*10)==a*10) return 1;
	return 2;
}

int main() {
	int n,m,s,b,t;
	cin>>n>>m>>s>>b>>t;
	for(int i=1; i<=m; i++) {
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(Edge {v,w*30});
		g[v].push_back(Edge {u,w*30});
	}
	dij(s,fromS);
	dij(t,toT);
	dij(b,fromB);
	int minDis=toT[s];
	double ans=9999999999,ans1=99999999999;
	int u=s;
	int flag=1;
	while(u!=t) {
		int mi=INT_MAX;
		for(Edge e:g[u]) {
			int v=e.v;
			if(fromS[v]+toT[v]==minDis&&!vis[v]) mi=min(mi,v);
		}
		if(fromS[mi]/2.0>=fromB[mi]/3.0) {
			flag=0;
			ans1=min(ans1,fromB[mi]/3.0+(fromS[mi]*1.0-fromB[mi]/3.0*2)/5.0);
		} else if(fromB[mi]-fromS[mi]/2.0*3 -toT[mi]/2.0<0){
			flag=0;
			ans1=min(ans1,fromS[mi]/2.0+(fromB[mi]-fromS[mi]/2.0*3));
		}else ans=min(ans,fromB[mi]-fromS[mi]/2.0*3 -toT[mi]/2.0);
		vis[u]=1;
		u=mi;
	}
	if(flag==0)
	{
		cout<<"NO\n";
		cout<<fixed<<setprecision(gp(ans1/30.0))<<ans1/30.0;
		return 0;
	}
	cout<<"YES\n";
	cout<<fixed<<setprecision(gp(ans/30.0))<<ans/30.0;
}
2022/12/26 16:08
加载中...