前三个点没过
dalao救一下XD
by Otion @ 2023-03-06 17:23:19
@[Otion](/user/843596) memset只能memset 0 和 -1
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
const int N = (int)1e5 * 2;
int total_area, total_road, start_area, target;
double dist[N];
int head[N];
int area[N];
int next_area[N];
double scale[N];
int idx;
double x[N];
double y[N];
bool state[N];
queue<int> line;
double fac(int area_1, int area_2)
{
int gap_x = x[area_1] - x[area_2];
int gap_y = y[area_1] - y[area_2];
gap_x *= gap_x;
gap_y *= gap_y;
double sum = gap_x + gap_y;
double shit = sqrt(sum);
return shit;
}
void add(int a, int b, double c)
{
area[idx] = b;
next_area[idx] = head[a];
head[a] = idx;
scale[idx] = c;
idx++;
}
void S_PFA()
{
dist[start_area] = 0;
line.push(start_area);
state[start_area] = 1;
while (line.size())
{
int origin = line.front();
line.pop();
state[origin] = 0;
for (int i = head[origin]; i != -1; i = next_area[i])
{
int now = area[i];
if (dist[now] > dist[origin] + scale[i])
{
dist[now] = dist[origin] + scale[i];
if (state[now] == 0)
{
line.push(now);
state[now] = 1;
}
}
}
}
}
int main()
{
memset(head, -1, sizeof(head));
memset(next_area, -1, sizeof(next_area));
for(int i = 0; i < N; i++) dist[i] = 100000;
cin >> total_area;
for (int i = 1; i <= total_area; i++)
{
int a, b;
cin >> a >> b;
x[i] = a;
y[i] = b;
}
cin >> total_road;
for (int i = 1; i <= total_road; i++)
{
int bind_1, bind_2;
cin >> bind_1 >> bind_2;
double scale = fac(bind_1, bind_2);
add(bind_1, bind_2, scale);
add(bind_2, bind_1, scale);
}
cin >> start_area >> target;
S_PFA();
// cout << dist[target] << endl;
printf("%.2lf", dist[target]);
return 0;
}
```
by Loser_Syx @ 2023-03-06 17:25:25
SPFA 小心挂掉，除了判负环最好用 dijkstra
by songszh @ 2023-03-06 17:32:07
@[Saint_ying_xtf](/user/852144) 谢谢dalao，关注啦
by Otion @ 2023-03-06 19:17:06