P1744 采购特价商品（SPFA求最短路径模板）

以你之姓@ 2023-01-07 12:25 52阅读 0赞

题目传送门：[https://www.luogu.com.cn/problem/P1744][https_www.luogu.com.cn_problem_P1744]

## 题意 ##

给出从  1 1 1 ~  N N N 编号的  N N N 个点，以及它们的坐标  ( x i ,   y i ) (x\_i,\\ y\_i) (xi, yi)，然后给出他们之间相连的  M M M 条边，最后给出起点的编号  S S S 和终点的编号  T T T，求它们之间的最短距离。

## 思路 ##

利用两点间距离的距离公式  ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \\sqrt\{(x\_1-x\_2)^2 + (y\_1-y\_2)^2\} (x1−x2)2\+(y1−y2)2，可以得到每一条边的权值，接下就是套最短路径的模板了。

由于 SPFA 能处理负权边的问题，而且我还不怎么会，这题就套用了 SPFA 的模板。它的处理流程如下：

*  初始化  d i s dis dis 数组元素到无穷大，将 dis\[s\] 置为 0；
 *  将原点  s s s 放入队列中；
    
     *  取出队首元素  u u u，遍历该点的所有连边  ( u , v , w ) (u,v,w) (u,v,w)；
     *  如果该边满足条件  d i s \[ v \] > d i s \[ u \] + w dis\[v\] > dis\[u\] + w dis\[v\]>dis\[u\]\+w，则更新  d i s \[ v \] dis\[v\] dis\[v\] 的值，并将  v v v 放入队列中。
     *  重复上面两步，直到队列为空，即没有点可以松弛。

注意：SPFA 会被经过特殊构造的数据卡掉，所以如果边权为正的时候，尽量选用 Dijkstra 算法求最短路径。

## 参考代码 ##

#include <iostream>
    #include <cstdio>
    #include <queue>
    #include <cmath>
    using namespace std;
    const int N = 1e2 + 10;
    const int M = 2e3 + 10;
    struct Edge { 
        int to, next;
        double w;
    } e[M];
    int n, m, s, t;
    int head[N], cnt;
    int x[N], y[N];
    double dis[N];
    bool vis[N];
    
    // 两点间距离公式
    double getDistance(int x1, int y1, int x2, int y2) { 
        return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }
    
    // 链式向前星
    int addEdge(int u, int v, double w) { 
        cnt++;
        e[cnt].to = v;
        e[cnt].w = w;
        e[cnt].next = head[u];
        head[u] = cnt;
    }
    
    // spfa 模板
    int spfa(int s) { 
        for (int i = 1; i <= n; i++) { 
            dis[i] = 1e9 + 7;
        }
        queue<int> q;
        q.push(s);
        vis[s] = true;
        dis[s] = 0;
        while (!q.empty()) { 
            int u = q.front();
            q.pop();
            vis[u] = false;
            for (int i = head[u]; i; i = e[i].next) { 
                int v = e[i].to;
                double w = e[i].w;
                if (dis[v] > dis[u] + w) { 
                    dis[v] = dis[u] + w;
                    if (!vis[v]) { 
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
    }
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++) { 
            cin >> x[i] >> y[i];
        }
        cin >> m;
        for (int i = 1; i <= m; i++) { 
            int u, v;
            cin >> u >> v;
            double w = getDistance(x[u], y[u], x[v], y[v]);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        cin >> s >> t;
        spfa(s);
        printf("%.2f\n", dis[t]);
        return 0;
    }

[https_www.luogu.com.cn_problem_P1744]: https://www.luogu.com.cn/problem/P1744