社区讨论
SPFA哇了三个点
P1744采购特价商品参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo30nj6n
- 此快照首次捕获于
- 2023/10/23 22:51 2 年前
- 此快照最后确认于
- 2023/10/23 22:51 2 年前
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));
memset(dist, (double)1000000, sizeof(dist));
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;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...