E. Rendez-vous de Marian et Robin

链接：https://codeforces.com/problemset/problem/2014/E
题面：

思路：
最短路首选dijkstra，这题也是这样，但是难点在于如何记录有马的时间这个状态。采取方法就是没有马的情况下正反跑一遍dijkstra，然后记录有马的位置的时间，从每个有马的地方重新dijkstra。拿四个数组，取ans = min ( ans , max (min(horse1,nohorse1),min(horsen,nohorsen) ) )
代码：

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
#include<map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

#define int long long 
const int INF = LLONG_MAX;
const int N = 2e5 + 3;
struct edge
{
	int from, to, w;
	bool horse;
	edge(){}
	edge(int a, int b, int v) { from = a, to = b; w = v; horse = false; }
	edge(int a, int b, int v,bool ax) { from = a, to = b; w = v; horse = ax; }

};
vector<edge>e[N];
vector<int>id;
struct node
{
	int id; int n_dis;
	node(int b, int c) { id = b, n_dis = c; }
	node(){}
	bool operator<(const node& a)const
	{
		return n_dis > a.n_dis;
	}
};
int n, m , h;
int disa[N], disf[N];
int disah[N], disfh[N];
bool done[N];
bool havehorse[N];
void dijkstraa()
{
	//先跑两个基础的dijk
	int  s = 1;
	for (int i = 1; i <= n; i++) { disa[i]=disah[i] = INF; done[i] = 0; }
	disa[s]= 0;
	if (havehorse[s])disah[s] = 0;
	priority_queue<node>Q;
	Q.push(node(s, disa[s]));
	while (!Q.empty())
	{
		node u = Q.top();
		Q.pop();
		if (done[u.id])continue;
		done[u.id] = true;
		for (int i = 0; i < e[u.id].size(); i++)
		{
			edge y = e[u.id][i];
			if (done[y.to])continue;
			if (disa[y.to] > y.w + u.n_dis)
			{
				disa[y.to] = y.w + u.n_dis;
				if (havehorse[y.to])disah[y.to] = disa[y.to];
				
				Q.push(node(y.to, disa[y.to]));
			}
		}
	}
	s = n;
	for (int i = 1; i <= n; i++) { disf[i]=disfh[i] = INF; done[i] = 0; }
	disf[s] = 0;
	if (havehorse[s])disfh[s] = 0;
	Q.push(node(s, disf[s]));
	while (!Q.empty())
	{
		node u = Q.top();
		Q.pop();
		if (done[u.id])continue;
		done[u.id] = 1;
		for (int i = 0; i < e[u.id].size(); i++)
		{
			edge y = e[u.id][i];
			if (done[y.to])continue;
			if (disf[y.to] > y.w + u.n_dis)
			{
				disf[y.to] = y.w + u.n_dis;
				if (havehorse[y.to])disfh[y.to] = disf[y.to];
				Q.push(node(y.to, disf[y.to]));
			}
		}
	}
	for (int v : id)
	{
		Q.push(node(v, disah[v]));
	}
	memset(done, 0, sizeof(done));
	while (!Q.empty())
	{
		node u = Q.top();
		Q.pop();
		if (done[u.id])continue;
		done[u.id] = true;
		for (int i = 0; i < e[u.id].size(); i++)
		{
			edge y = e[u.id][i];
			if (done[y.to])continue;
			if (disah[y.to] > y.w / 2 + u.n_dis)
			{
				disah[y.to] = y.w / 2 + u.n_dis;
				Q.push(node(y.to, disah[y.to]));
			}
		}
	}
	for (int v : id)
	{
		Q.push(node(v, disfh[v]));
	}
	memset(done, 0, sizeof(done));
	while (!Q.empty())
	{
		node u = Q.top();
		Q.pop();
		if (done[u.id])continue;
		done[u.id] = true;
		for (int i = 0; i < e[u.id].size(); i++)
		{
			edge y = e[u.id][i];
			if (done[y.to])continue;
			if (disfh[y.to] > y.w / 2 + u.n_dis)
			{
				disfh[y.to] = y.w / 2 + u.n_dis;
				Q.push(node(y.to, disfh[y.to]));
			}
		}

	}

}

void init()
{
	memset(havehorse, 0, sizeof(havehorse));
	memset(done, 0, sizeof(done));
	id.clear();
	for (int i = 0; i <= n; i++)e[i].clear();
}
signed main()
{
	IOS;
	int t; cin >> t;
	while (t--)
	{
		cin >> n >> m >> h;
		init();
		for (int i = 0; i < h; i++) { int x; cin >> x; id.push_back(x); havehorse[x] = 1; }
		for (int i = 0; i < m; i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			e[u].push_back(edge(u, v, w));
			e[v].push_back(edge(v, u, w));
		}
		dijkstraa();
		int ans = LLONG_MAX;
		for (int i = 1; i <= n; i++)
		{
			if (disa[i] != INF and disf[i] != INF )
			{
				int mini = min(disfh[i], disf[i]);
				int minisc = min(disa[i], disah[i]);
				ans = min(ans, max(mini,minisc));
			}
		}
		if (ans == INF)cout << -1 << '\n';
		else cout << ans << '\n';


	}
	return 0;
}

这也太长了些