70pts求助!sub3全WAT_T
查看原帖
70pts求助!sub3全WAT_T
183881
_shy楼主2022/12/26 11:14
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int n, m, s, b, f;
int head[maxn], cnt;
double ians = 2147483647, ans = 2147483647;
struct edge 
{
	int v, w, next;
} e[maxn << 1];
void add (int u, int v, int w) 
{
	e[++ cnt] = (edge) {v, w, head[u]};
	head[u] = cnt;
} 
struct node 
{
	int pos, dist;
	bool operator < (node a) const 
	{
		return a.dist < dist;
	}
};
priority_queue <node> q, emptyi;
int dis[2][maxn], vis[maxn], path[maxn], l[maxn], tot[maxn];
void dijkstra (int si, int tp) 
{
	memset (vis, 0, sizeof (vis));
	memset (dis[tp], 0x7f7f7f7f, sizeof (dis[tp]));
	q = emptyi;
	dis[tp][si] = 0;
	if (tp == 0) tot[si] = 1;
	q.push ((node) {si, 0}); 
	while (!q.empty ()) 
	{
		int u = q.top ().pos;
		q.pop ();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = head[u]; i; i = e[i].next) 
		{
			int v = e[i].v, w = e[i].w;
			if (vis[v]) continue;
			if (dis[tp][v] > dis[tp][u] + w) 
			{
				dis[tp][v] = dis[tp][u] + w;
				q.push ((node) {v, dis[tp][v]});
				if (tp == 0)
					path[v] = u, l[v] = l[u] + w, tot[v] = tot[u] + 1;
			}
			else if (tp == 0 && dis[tp][v] == dis[tp][u] + w) 
			{
				int a = u, b = path[v], tota = tot[a], totb = tot[b];
				while (tota > totb) a = path[a], tota --;
				while (totb > tota) b = path[b], totb --;
				while (path[a] != path[b]) 
					a = path[a], b = path[b];
				if (a < b) path[v] = u, l[v] = l[u] + w, tot[v] = tot[u] + 1; 
			}
		} 
	}
}
int main ()
{
	scanf ("%d %d %d %d %d", &n, &m, &s, &b, &f);
	for (int i = 1; i <= m; i++) 
	{
		int u, v, w;
		scanf ("%d %d %d", &u, &v, &w);
		add (u, v, w), add (v, u, w);
	}
	dijkstra (s, 0);
	dijkstra (b, 1);
	int v = f, flag = 0;
	while (v != 0) 
	{
		double ansi = dis[1][v] / 3.0;
		if (ansi == l[v] / 2.0) 
			flag = 1, ans = min (ansi, ans);
		else if (ansi * 2.0 < l[v]) 
		{
			double ansii = (l[v] - ansi * 2.0) / 5.0;
			flag = 1, ans = min (ans, ansi + ansii);
		}
		else 
		{
			if (ansi > l[f] / 2.0 && flag == 0) 
				ians = min (ians, l[f] - l[v] + 3.0 * (ansi - l[f] / 2.0));
			else 
			{
				double ansii = (2.0 * ansi - l[v]);
				if (ansii <= (l[f] - 2 * ansi) / 2.0) 
					flag = 1, ans = min (ans, ansii + ansi);
				else if (ansii > (l[f] - 2 * ansi) / 2.0 && flag == 0)
					ians = min (ians, l[f] - l[v] - 3.0 * (l[f] - 2 * ansi) / 2.0);
			} 
		}
		v = path[v];
	}
	if (!flag) printf ("YES\n"), ans = ians;
	else printf ("NO\n");
	cout << ans;
	return 0;
}


2022/12/26 11:14
加载中...