社区讨论

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 条回复,欢迎继续交流。

正在加载回复...