題目傳送門：https://www.luogu.com.cn/problem/P1744

題意

給出從 $1$ ~ $N$ 編號的 $N$ 個點，以及它們的坐標 $(x_i,y_i)$，然后給出他們之間相連的 $M$ 條邊，最后給出起點的編號 $S$ 和終點的編號 $T$，求它們之間的最短距離。

思路

利用兩點間距離的距離公式 $\sqrt{(x_1?x_2{)}^2+(y_1?y_2{)}^2}$，可以得到每一條邊的權值，接下就是套最短路徑的模板了。

由于 SPFA 能處理負權邊的問題，而且我還不怎么會，這題就套用了 SPFA 的模板。它的處理流程如下：

• 初始化 $dis$ 數組元素到無窮大，將 dis[s] 置為 0；
• 將原點 $s$ 放入隊列中；
  • 取出隊首元素 $u$，遍歷該點的所有連邊 $(u,v,w)$；
  • 如果該邊滿足條件 $dis[v]>dis[u]+w$，則更新 $dis[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; }

總結

以上是生活随笔為你收集整理的P1744 采购特价商品（SPFA求最短路径模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。