图论有时候不那么显然

懵逼的 题目

传送至 Luogu

扯淡的 题解

一眼题, 求路径最大值最小, 随便跑跑dijk或者SPFA都行, dijk甚至不用优化…
一开始初始化炸了, 没有把半径除以2
然后我堆优化写炸了

我写的是酱的:

struct cmp
{
    bool operator () (int x, int y)
    {
        return dis[x] > dis[y];
    }
};

void dijk(int startDash)
{
    dis[startDash] = 0;
    priority_queue<int, vector<int>, cmp> q;
    q.push(startDash);
    while (!q.empty())
    {
        int dq = q.top();
        q.pop();
        if (vis[dq])
            continue;
        vis[dq] = true;
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (max(dis[dq], b[i].cost) < dis[b[i].to])
            {
                dis[b[i].to] = max(dis[dq], b[i].cost);
                q.push(b[i].to);
            }
        }
    }
}

然后在40 50之间徘徊
写了个SPFA, A了
dijk始终A不了
不解, 后来终于有学长(无限仰慕orz)告诉我酱是不行的, 当priority_queue重载的全局变量时dis即使变化, 优先队列的顺序也不会改变…
然后改成了酱

struct cmp
{
    bool operator () (pair<int, DD> x, pair<int, DD> y)
    {
        return x.second > y.second;
    }
};

void dijk(int startDash)
{
    dis[startDash] = 0;
    priority_queue<pair<int, DD>, vector<pair<int, DD> >, cmp> q;
    q.push(make_pair(startDash, 0));
    while (!q.empty())
    {
        pair<int, DD> dq = q.top();
        q.pop();
        if (vis[dq.first])
            continue;
        vis[dq.first] = true;
        for (int i = g[dq.first]; i; i = b[i].next)
        {
            if (max(dq.second, b[i].cost) < dis[b[i].to])
            {
                dis[b[i].to] = max(dis[dq.first], b[i].cost);
                q.push(make_pair(b[i].to, dis[b[i].to]));
            }
        }
    }
}

A了

还是基础不牢啊…
初中教练的话都应验了啊…

沙茶的 代码

SPFA

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN (800 + 5)
#define MAXL (1000 + 5)
#define INF (0x7fffffff)
#define DD double
int S;
int T;
using namespace std;
struct edg
{
    int from;
    int to;
    DD cost;
    int next;
}b[(MAXN * MAXN) << 1];
int cntb;
int g[MAXN];

struct tower
{
    int h;
    int l;
}a[MAXN];

int n;
int l;

DD dis[MAXN];
bool vis[MAXN];
DD js(int, int, int, int);
void dijk(int);
void init();
void adn(int, int, DD);
void spfa(int);
int main()
{
    init();
    dijk(S);
//    spfa(S);
    printf("%.2lf", dis[T]);
    return 0;
}
DD js(int x1, int y1, int x2, int y2)
{
    int dx = x1 - x2;
    int dy = y1 - y2;
    return sqrt(dx * dx + dy * dy);
}
void adn(int from, int to, DD cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
void init()
{
    scanf("%d%d", &l, &n);
    S = n + 2;
    T = n + 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].l, &a[i].h);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            DD c = js(a[i].h, a[i].l, a[j].h, a[j].l);
            c /= 2;
            adn(i, j, c);
        }
        adn(S, i, a[i].l + 1);
        adn(i, S, a[i].l + 1);
        adn(T, i, l - a[i].l + 1);
        adn(i, T, l - a[i].l + 1);
    }
    for (int i = 1; i <= n + 1; i++)
    {
        dis[i] = INF;
    }
    memset(vis, false, sizeof(vis));
}
void spfa(int startDash)
{
    dis[startDash] = 0;
    queue<int> q;
    q.push(startDash);
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        vis[dq] = false;
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (max(dis[dq], b[i].cost) < dis[b[i].to])
            {
                dis[b[i].to] = max(dis[dq], b[i].cost);
                if (!vis[b[i].to])
                {
                    q.push(b[i].to);
                    vis[b[i].to] = true;
                }
            }
        }
    }
}


/*
5 5
1 5
3 5
5 5
4 30
2 15


100 2
30 50
90 100
*/

/*
4 5
1 0
1 15
2 5
2 15
4 10
*/

堆优化 dijk

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN (800 + 5)
#define MAXL (1000 + 5)
#define INF (0x7fffffff)
#define DD double
int S;
int T;
using namespace std;
struct edg
{
    int from;
    int to;
    DD cost;
    int next;
}b[(MAXN * MAXN) << 1];
int cntb;
int g[MAXN];

struct tower
{
    int h;
    int l;
}a[MAXN];

int n;
int l;

bool vis[MAXN];
DD dis[MAXN];
struct cmp
{
    bool operator () (pair<int, DD> x, pair<int, DD> y)
    {
        return x.second > y.second;
    }
};

DD js(int, int, int, int);
void dijk(int);
void init();
void adn(int, int, DD);
void spfa(int);
int main()
{
    init();
    dijk(S);
//    spfa(S);
    printf("%.2lf", dis[T]);
    return 0;
}
DD js(int x1, int y1, int x2, int y2)
{
    int dx = x1 - x2;
    int dy = y1 - y2;
    return sqrt(dx * dx + dy * dy);
}
void adn(int from, int to, DD cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
void init()
{
    scanf("%d%d", &l, &n);
    S = n + 2;
    T = n + 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].l, &a[i].h);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            DD c = js(a[i].h, a[i].l, a[j].h, a[j].l);
            c /= 2;
            adn(i, j, c);
        }
        adn(S, i, a[i].l);
        adn(i, S, a[i].l);
        adn(T, i, l - a[i].l + 1);
        adn(i, T, l - a[i].l + 1);
    }
    for (int i = 1; i <= n + 1; i++)
    {
        dis[i] = INF;
    }
    memset(vis, false, sizeof(vis));
}
void dijk(int startDash)
{
    dis[startDash] = 0;
    priority_queue<pair<int, DD>, vector<pair<int, DD> >, cmp> q;
    q.push(make_pair(startDash, 0));
    while (!q.empty())
    {
        pair<int, DD> dq = q.top();
        q.pop();
        if (vis[dq.first])
            continue;
        vis[dq.first] = true;
        for (int i = g[dq.first]; i; i = b[i].next)
        {
            if (max(dq.second, b[i].cost) < dis[b[i].to])
            {
                dis[b[i].to] = max(dis[dq.first], b[i].cost);
                q.push(make_pair(b[i].to, dis[b[i].to]));
            }
        }
    }
}


/*
5 5
1 5
3 5
5 5
4 30
2 15


100 2
30 50
90 100
*/

/*
4 5
1 0
1 15
2 5
2 15
4 10
*/

By Cansult

胸を张って 全て夸れる!