今天讲讲1342。
1342：【例4-1】最短路径问题
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 8712 通过数: 3862
【题目描述】
平面上有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
思路：floyd。
代码：
#include <bits/stdc++.h>
using namespace std;
double a[150][150],x[105],y[105];
int n,s,t,m,p,q;
void floyd()//floyd算法算最短路径
{
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
if(i!=k)
for(int j=1; j<=n; j++)
if(i!=j&&j!=k&&a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];
}
int main()
{
memset(a,0x7F,sizeof(a));//赋最大值
cin>>n;
for(int i=1; i<=n; i++)
cin>>x[i]>>y[i];
cin>>m;//输入
for(int i=1; i<=m; i++)
{
cin>>p>>q;
a[p][q]=sqrt((double)(x[p]-x[q])*(x[p]-x[q])+(double)(y[p]-y[q])*(y[p]-y[q]));//计算长度
a[q][p]=a[p][q];//别忘了反一反
}
cin>>s>>t;
floyd();//floyd算法
cout<<fixed<<setprecision(2)<<a[s][t]<<endl;//输出
return 0;
}
最近有点忙，不过还好，再见。
