翻车笔记_ luogu1783 海滩防御 [最短路]

图论有时候不那么显然

懵逼的 题目

传送至 Luogu

扯淡的 题解

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

我写的是酱的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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即使变化, 优先队列的顺序也不会改变…
然后改成了酱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#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

胸を张って 全て夸れる!