目錄
- T1. 最短路徑問題
-
- 思路分析
- T2. Freda 的越野跑
-
- 思路分析
- T3. 社交網絡
-
- 思路分析
- T4. 旅行
-
- 思路分析
T1. 最短路徑問題
題目鏈接：SOJ D1249
平面上有 n n n 個點（ n ≤ 100 n\le 100 n≤100），每個點的坐標均在 ? 10000 ～ 10000 -10000\sim 10000 ?10000～10000 之間。其中的一些點之間有連線。若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離。現在的任務是找出從一點到另一點之間的最短路徑。
時間限制：1 s
內存限制：128 MB
- 輸入
共 n + m + 3 n+m+3 n+m+3 行，第一行為整數 n n n。
第 2 2 2 行到第 n + 1 n+1 n+1 行（共 n n n 行） ，每行兩個整數 x x x 和 y y y，描述了一個點的坐標。
第 n + 2 n+2 n+2 行為一個整數 m m m，表示圖中連線的個數。
此后的 m m m 行，每行描述一條連線，由兩個整數 i i i 和 j j j 組成，表示第 i i i 個點和第 j j j 個點之間有連線。
最后一行兩個整數 s s s 和 t t t，分別表示源點和目標點。 - 輸出
僅一行，一個實數（保留兩位小數），表示從 s s s 到 t t t 的最短路徑長度。 - 樣例輸入
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 - 樣例輸出
3.41
思路分析
此題考查最短路徑問題，屬于模板題。常規情況下，最好選用 D i j k s t r a \tt Dijkstra Dijkstra 算法進行求解，不過此題數據量較小，可以使用代碼更為簡單的 F l o y d \tt Floyd Floyd 算法求解。
/** Name: T1.cpp* Problem: 最短路徑問題* Author: Teacher Gao.* Date&Time: 2025/07/18 15:25*/#include <iostream>
#include <cmath>using namespace std;int x[105], y[105];
double g[105][105];double dis(int u, int v) {return sqrt((x[u] - x[v]) * (x[u] - x[v]) + (y[u] - y[v]) * (y[u] - y[v]));
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int n, m, u, v;fill(g[0], g[0] + 105 * 105, 1e9);cin >> n;for (int i = 1; i <= n; i++) {cin >> x[i] >> y[i];g[i][i] = 0;}cin >> m;for (int i = 1; i <= m; i++) {cin >> u >> v;g[u][v] = g[v][u] = dis(u, v);}for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (g[i][j] > g[i][k] + g[k][j])g[i][j] = g[i][k] + g[k][j];cin >> u >> v;printf("%.2lf", g[u][v]
)
