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