A38162. 最短路径问题平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。输入共n+m+3行，其中: 第一行为整数n。 第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。 第n+2行为一个整数m，表示图中…
填空题
困难
知识点
题目描述
最短路径问题
平面上有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的最短路径长度。
样例输入
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
参考答案
#include<iostream>
#include<cmath>
using namespace std;
struct p {
int x,y;
}
a[102];
int f[102][102];
double k[102][102];
int main() {
int b,e;
int n;
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
int m;
cin>>m;
for (int i=1;i<=m;i++) {
int x,y;
cin>>x>>y;
f[x][y]=f[y][x]=1;
}
cin>>b>>e;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if(f[i][j])//如果两点有连接
k[i][j]=sqrt(pow((double)(a[i].x-a[j].x),2.0)+pow((double)(a[i].y-a[j].y),2.0));
//求两点距离，存入k数组 else
k[i][j]=0x7fffffff;
//反之则设为极大值
for (int p=1;p<=n;p++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if(k[i][j]>k[i][p]+k[p][j])
k[i][j]=k[i][p]+k[p][j];
//开始算法
cout<<k[b][e];
//输出从起点（b）到终点（e）的最短路径
system("pause");
return 0;
}
上一题
下一题