0130B

Done IOI Start at: 2026-1-30 8:30 3 hour(s) Host: 56
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 810;
const int M = N * N + 2 * N;
int n, m;
int head[N], ver[M], nxt[M], tot;
double f[N], edge[M];
bool vis[N];
int x[N], y[N];

void add(int x, int y, double z) {
	tot++;
	ver[tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
	edge[tot] = z;
}

void dijkstra() {
	for (int i = 0; i <= m + 1; i++)
		f[i] = 1e9;
	f[0] = 0;
	priority_queue<pair<double, int>>q;
	q.push({0, 0});
	while (q.size()) {
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (int i = head[u] ; i ; i = nxt[i]) {
			int v = ver[i];
			double w = edge[i];
			if (f[v] > max(f[u], w)) {
				f[v] = max(f[u], w);
				q.push({-f[v], v});
			}
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> x[i] >> y[i];
	for (int i = 1; i <= m; i++) {
		add(0, i, x[i]);
		add(i, 0, x[i]);
		add(m + 1, i, n - x[i]);
		add(i, m + 1, n - x[i]);
	}
	for (int i = 1; i < m; i++) {
		for (int j = i + 1; j <= m; j++) {
			double len = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
			add(i, j, len / 2);
			add(j, i, len / 2);
		}
	}
	dijkstra();
	cout << fixed << setprecision(2) << f[m + 1] << '\n';
	return 0;
}

// 建立 0 点连接所有的僵尸点,边权为0
// 0 点跑 dijkstra ,
// 对所有的僵尸点连接一个虚点
// 先跑一遍最短路,求出最短距离,确定花费
// 然后再从 1 到 N跑最短路

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 4e5 + 10 + N;
#define int long long
int n, m, k, s;
int P, Q; // p 安全, q 不安全
int st[N]; // 标记当前点到僵尸点的距离
int head[N], ver[M], nxt[M], tot, edge[M];
int f[N];
bool vis1[N]; // 标记传染源,传染源不能进入
bool vis[N];

void add(int x, int y, int z) {
	tot++;
	ver[tot] = y;
	edge[tot] = z;
	nxt[tot] = head[x];
	head[x] = tot;
}

// 从虚拟点 0 点开始搜索
void dijkstra() {
	memset(st, 0x7f, sizeof st);
	memset(vis, 0, sizeof vis);
	st[0] = 0;
	priority_queue<pair<int, int> >q;
	q.push({0, 0});
	while (q.size()) {
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (int i = head[u] ; i  ; i = nxt[i]) {
			int v = ver[i];
			int w = edge[i];
			if (st[v] > st[u] + w) {
				st[v] = st[u] + w;
				q.push({-st[v], v});
			}
		}
	}
}

void dijkstra1() {
	memset(f, 0x7f, sizeof f);
	memset(vis, 0, sizeof vis);
	f[1] = 0;
	priority_queue<pair<int, int> >q;
	q.push({0, 1});
	while (q.size()) {
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (int i = head[u] ; i; i = nxt[i]) {
			int v = ver[i];
			if (v == 0)
				continue; // 建立的虚拟点
			if (vis1[v])
				continue; // 传染源不能进入
			// 距离不超过 s 就是危险城市
			int w = st[v] <= s ? Q : P;
			if (v == n)
				w = 0;
			if (f[v] > f[u] + w) {
				f[v] = f[u] + w;
				q.push({-f[v], v});
			}
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> k >> s;
	cin >> P >> Q;
	for (int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		vis1[x] = 1;
		add(0, x, 0); // 建立从 0 点到所有僵尸点的边
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y, 1);
		add(y, x, 1);
	}
	dijkstra(); // 从 点 0 开始跑
	st[1] = 1e9, st[n] = 1e9;
	dijkstra1();
	cout << f[n];
	return 0;
}
Status
Done
Rule
IOI
Problem
5
Start at
2026-1-30 8:30
End at
2026-1-30 11:30
Duration
3 hour(s)
Host
Partic.
56