题目描述 平面上有 n 个点 (n≤100)，每个点的坐标均在 −10000∗10000 之间。其中的一些点之间有连线。 若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。 现在的任务是找出从一点到另一点之间的最短路径。 输入 输入共 n+m+3 行，其中: 第一行为整数 n。 第 2 行到第 n+1 行（共 n 行） ，每行两个整数 x 和 y，描述了一个点的坐标。 第 n+2 行为一个整数 m，表示图中连线的个数。 此后的 m 行，每行描述一条连线，由两个整数 i 和 j 组成，表示第 i 个点和第 j 个点之间有连线。 最后一行：两个整数 s 和 t，分别表示源点和目标点。 输出 输出仅一行，一个实数（保留两位小数），表示从 s 到 t 的最短路径长度。 样例输入 Copy 5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 样例输出 Copy 3.41

这道题目是一个典型的最短路径问题，可以用 Dijkstra 算法或是 Floyd 算法来解决。

首先，输入点的个数和点的坐标，可以用一个结构体来存储，每个结构体包含点的编号和坐标。

struct Point {
    int id;
    double x, y;
};

由于点之间有连线，可以用邻接矩阵来表示图。如果两个点之间有连线，则邻接矩阵中对应的元素为两点之间的距离，否则为无穷大。

const double INF = 1e8;
double dis[MAXN][MAXN];
// 初始化邻接矩阵
for (int i = 0; i < MAXN; i++) {
    for (int j = 0; j < MAXN; j++) {
        if (i == j) {
            dis[i][j] = 0;
        } else {
            dis[i][j] = INF;
        }
    }
}
for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    // 计算两点之间的距离
    double d = sqrt(pow(points[x].x - points[y].x, 2) + pow(points[x].y - points[y].y, 2));
    dis[x][y] = dis[y][x] = d;
}

接下来，可以用 Dijkstra 算法或是 Floyd 算法来求解最短路径。

Dijkstra 算法是一种贪心算法，每次从未确定最短路径的点集中选取距离源点最近的点，然后更新与该点相邻的点的距离。直到所有点都被确定最短路径为止。

double dijkstra(int s, int t) {
    bool vis[MAXN] = {0}; // 标记是否已确定最短路径
    double d[MAXN]; // 存储源点到各个点的距离
    for (int i = 0; i < MAXN; i++) {
        d[i] = dis[s][i];
    }
    vis[s] = true;
    for (int i = 1; i < n; i++) { // 确定 n-1 个点的最短路径
        double minDis = INF;
        int v;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && d[j] < minDis) {
                minDis = d[j];
                v = j;
            }
        }
        vis[v] = true;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && d[v] + dis[v][j] < d[j]) {
                d[j] = d[v] + dis[v][j];
            }
        }
    }
    return d[t];
}

Floyd 算法是一种动态规划算法，每次考虑是否经过一个中间点，可以得到点之间的最短路径。具体实现如下：

void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

完整代码如下：