face-to-face road

题目链接：UNR #6 A

题目大意

给你一个无向图,Then each edge has a length,然后你在 1 号点,有不超过 20 Individuals at their respective points,Each person can walk one unit of length per unit of time.
Then ask how long it will take you at least to meet everyone in turn.（可以在边上）

思路

First find the order is ok,Just want these people to reconcile.
And then found out that he wasn't special either,So the problem is the time to get to a place $\max$ 取 $\min$.

（Run directly at each point as the starting point dij Get the distance to each location）
Each point can then be enumerated first,Then consider the edges.
Consider getting a demarcation point,If the distance to the left point is less than or equal to the dividing point,Then go to the point on the left,Otherwise go to the point on the right.
The dividing point only needs to enumerate the distance from each point to the left point.

然后好了.

代码

#include<queue> 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 1e5 + 100;
struct node {
    
	int x, to, nxt;
}e[N << 2];
int n, m, k, pl[21], X[N << 1], Y[N << 1], Z[N << 1], le[N], KK;
ll dis[21][N], ans;
priority_queue <pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;
bool in[N];

void add(int x, int y, int z) {
    e[++KK] = (node){
    z, y, le[x]}; le[x] = KK;} 

void get_dis(ll *dis, int S) {
    
	while (!q.empty()) q.pop(); q.push(make_pair(0, S));
	dis[S] = 0;
	memset(in, 0, sizeof(in));
	while (!q.empty()) {
    
		int now = q.top().second; q.pop();
		if (in[now]) continue; in[now] = 1;
		for (int i = le[now]; i; i = e[i].nxt)
			if (dis[e[i].to] > dis[now] + e[i].x) {
    
				dis[e[i].to] = dis[now] + e[i].x;
				q.push(make_pair(dis[e[i].to], e[i].to));
			}
	}
}

int main() {
    
// freopen("ex_trip4.in", "r", stdin);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
    
		int x, y, z; scanf("%d %d %d", &x, &y, &z); z *= 2; X[i] = x; Y[i] = y; Z[i] = z;
		add(x, y, z); add(y, x, z);
	}
	scanf("%d", &k); for (int i = 1; i <= k; i++) scanf("%d", &pl[i]); pl[0] = 1;
	
	memset(dis, 0x7f, sizeof(dis));
	for (int i = 0; i <= k; i++) get_dis(dis[i], pl[i]);
	
	ans = INF;
	for (int i = 1; i <= n; i++) {
    
		ll now = 0; for (int j = 0; j <= k; j++) now = max(now, dis[j][i]);
		ans = min(ans, now);
	}
	for (int i = 1; i <= m; i++) {
    
		int x = X[i], y = Y[i], z = Z[i];
		for (int j = 0; j <= k; j++) {
    
			ll now1 = 0, now2 = 0;
			for (int jj = 0; jj <= k; jj++)
				if (dis[jj][x] <= dis[j][x]) now1 = max(now1, dis[jj][x]);
					else now2 = max(now2, dis[jj][y]);
			if (now1 > now2) swap(now1, now2);
			if (now1 + z <= now2) ans = min(ans, now2);
				else ans = min(ans, (now1 + now2 + z) / 2);
		}
	}
	printf("%lld", ans);
	
	return 0;
}