题目描述
题目背景
《爱与愁的故事第三弹·shopping》第一章。
题目描述
中山路店山店海，成了购物狂爱与愁大神的“不归之路”。中山路上有 n 家店，每家店的坐标均在 -10000~10000 之间。其中的 m 家店之间有通路。若有通路，则表示可以从一家店走到另一家店，通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗？
输入格式
共 n + m + 3 行：
- 第 1 行：整数
n，表示店的数量。 - 第 2 行 ~ 第 n+1 行：每行两个整数
x和y，描述了一家店的坐标。 - 第 n+2 行：整数
m，表示有通路的店的对数。 - 第 n+3 行 ~ 第 n+m+2 行：每行描述一条通路，由两个整数
i和j组成，表示第i家店和第j家店之间有通路。 - 第 n+m+3 行：两个整数
s和t，分别表示起点店和目标店。
输出格式
仅一行：一个实数（保留两位小数），表示从 s 到 t 的最短路径长度。
样例数据
输入 #1
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
输出 #1
3.41
样例解释： 有 5 家店，根据坐标可以算出有通路连接的店之间的直线距离。从店 1 到店 5 的最短路径是 1 → 2 → 5（或 1 → 3 → 5），总距离为 3.41。
数据范围
n ≤ 100m ≤ 1000
实现
边的权重需要你自己用“两点间距离公式”计算。
#include <bits/stdc++.h>
using namespace std;const double INF = 1e20; // 定义无穷大int n, m, x[102], y[102];
bool visited[102];
double v[104][104], dist[104];double Dis(int t1, int t2) {return sqrt((x[t1] - x[t2]) * (x[t1] - x[t2]) + (y[t1] - y[t2]) * (y[t1] - y[t2]));
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];// 初始化邻接矩阵为无穷大for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)v[i][j] = (i == j) ? 0 : INF; // 自己到自己的距离为0scanf("%d", &m);for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;double d = Dis(a, b);v[a][b] = v[b][a] = d;}int s, t;cin >> s >> t;for (int i = 1; i <= n; i++) dist[i] = 0x3fffffff;dist[s] = 0;for (int k = 1; k < n; k++) {int Min = 0x3fffffff, id = 0;for (int i = 1; i <= n; i++) {if (!visited[i] && Min > dist[i]) {Min = dist[i];id = i;}}visited[id] = 1;for (int i = 1; i <= n; i++) {// 只有存在边（v[id][i] < INF）时才进行松弛if (!visited[i] && v[id][i] < INF && dist[i] > dist[id] + v[id][i]) {dist[i] = dist[id] + v[id][i];}}}printf("%.2lf\n", dist[t]);return 0;
}