目录
- 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]
)
