建议加强数据，本题目前的数据得到的最短路径是唯一的。
查看原帖
建议加强数据，本题目前的数据得到的最短路径是唯一的。
183881
_shy楼主2022/12/27 14:17

这个代码已AC，但根本没有求字典序最短的路径，只是单纯的记录了路径，但是也过了！说明数据较水（？）

#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;
const double eps = 1e-3;
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];
void dijkstra (int si, int tp) 
{
	memset (vis, 0, sizeof (vis));
	memset (dis[tp], 0x7f7f7f7f, sizeof (dis[tp]));
	q = emptyi;
	dis[tp][si] = 0;
	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;
			}
		
		} 
	}
}
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 (f, 0);
	dijkstra (b, 1);
	int v = s, flag = 0;
	while (v != 0) 
	{
		if (dis[1][v] == 2147483647) continue; 
		double ansi = dis[1][v] / 3.0;
		if (ansi == (dis[0][s] - dis[0][v]) / 2.0) 
			flag = 1, ans = min (ansi, ans);
		else if (ansi * 2.0 < dis[0][s] - dis[0][v]) 
		{
			double ansii = (dis[0][s] - dis[0][v] - ansi * 2.0) / 5.0;
			flag = 1, ans = min (ans, ansi + ansii);
		}
		else 
		{
			if (ansi > dis[0][s] / 2.0 && flag == 0) 
				ians = min (ians, dis[0][v] + 3.0 * (ansi - dis[0][s] / 2.0));
			else 
			{
				double ansii = (2.0 * ansi + dis[0][v] - dis[0][s]);
				if (ansii <= (dis[0][s] - 2 * ansi) / 2.0) 
					flag = 1, ans = min (ans, ansii + ansi);
				else if (ansii > (dis[0][s] - 2 * ansi) / 2.0 && flag == 0)
					ians = min (ians, dis[0][v] - 3.0 * (dis[0][s] - 2 * ansi) / 2.0);
			} 
		}
		v = path[v];
	}
	if (!flag) printf ("YES\n"), ans = ians;
	else printf ("NO\n");
	long long x = (ans + eps) * 100;
    if (x % 100 == 0) printf("%lld", x / 100);
    else if (x % 10 == 0) printf("%.1lf", 0.01 * x);
    else printf("%.2lf", 0.01 * x);
	return 0;
}

另外，窃以为以S为起点，F为终点，更新前驱数组是错误的；应当以F为起点，S为终点，更新前驱数组，得到的才是字典序最小的最短路径。代码如下：

#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;
const double eps = 1e-3;
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];
void dijkstra (int si, int tp) 
{
	memset (vis, 0, sizeof (vis));
	memset (dis[tp], 0x7f7f7f7f, sizeof (dis[tp]));
	q = emptyi;
	dis[tp][si] = 0;
	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;
			}
			else if (tp == 0 && dis[tp][v] == dis[tp][u] + w) 
				path[v] = min (path[v], u);
		} 
	}
}
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 (f, 0);
	dijkstra (b, 1);
	int v = s, flag = 0;
	while (v != 0) 
	{
		if (dis[1][v] == 2147483647) continue; 
		double ansi = dis[1][v] / 3.0;
		if (ansi == (dis[0][s] - dis[0][v]) / 2.0) 
			flag = 1, ans = min (ansi, ans);
		else if (ansi * 2.0 < dis[0][s] - dis[0][v]) 
		{
			double ansii = (dis[0][s] - dis[0][v] - ansi * 2.0) / 5.0;
			flag = 1, ans = min (ans, ansi + ansii);
		}
		else 
		{
			if (ansi > dis[0][s] / 2.0 && flag == 0) 
				ians = min (ians, dis[0][v] + 3.0 * (ansi - dis[0][s] / 2.0));
			else 
			{
				double ansii = (2.0 * ansi + dis[0][v] - dis[0][s]);
				if (ansii <= (dis[0][s] - 2 * ansi) / 2.0) 
					flag = 1, ans = min (ans, ansii + ansi);
				else if (ansii > (dis[0][s] - 2 * ansi) / 2.0 && flag == 0)
					ians = min (ians, dis[0][v] - 3.0 * (dis[0][s] - 2 * ansi) / 2.0);
			} 
		}
		v = path[v];
	}
	if (!flag) printf ("YES\n"), ans = ians;
	else printf ("NO\n");
	long long x = (ans + eps) * 100;
    if (x % 100 == 0) printf("%lld", x / 100);
    else if (x % 10 == 0) printf("%.1lf", 0.01 * x);
    else printf("%.2lf", 0.01 * x);
	return 0;
}
2022/12/27 14:17