【图论】【最短路】最短路径问题
程序员文章站
2023-12-27 13:55:57
...
Description
平面上有n个点(N<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点直线的距离。现在的任务是找出从一点到另一点之间的最短路径。
Input
输入文件short.in,共有n+m+3行,其中:
第一行为一个整数n。
第2行到第n+1行(共n行),每行的两个整数x和y,描述一个点的坐标(以一个空格隔开)。
第n+2行为一个整数m,表示图中的连线个数。
此后的m行,每行描述一条连线,由两个整数I,j组成,表示第i个点和第j个点之间有连线。
最后一行:两个整数s和t,分别表示源点和目标点。
Output
输出文件short.out仅一行,一个实数(保留两位小数),表示从S到T的最短路径的长度。
Sample Input
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
Sample Output
3.41
解题思路
最短路模板,输入的时候需要用公式 求出两个连接的点的距离(边权)
Ford算法
未更新的为蓝点,更新过的为白点
~
从出发,标记为白点
~
枚举所有的边
更新了
再次枚举所有边,白点并不限制更新对象,既可以更新蓝点也可以更新白点
更新了
更新了
至此,最短路就求完了(✿✿ヽ(°▽°)ノ✿)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,S,T,x[2000],y[2000],lx[2000],ly[2000];
double s[2000],dis[2000];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&lx[i],&ly[i]);
s[i]=sqrt(pow(double(x[lx[i]]-x[ly[i]]),2)+pow(double(y[lx[i]]-y[ly[i]]),2));//求边权
}
scanf("%d%d",&S,&T);
memset(dis,0x7f,sizeof(dis));
dis[S]=0;//起点设为0
for(int i=1;i<n;i++){//
bool t=0;
for(int j=1;j<=m;j++){
if(dis[lx[j]]+s[j]<dis[ly[j]]){//
dis[ly[j]]=dis[lx[j]]+s[j];//
t=1; //
} //判断这条边可不可以松弛连接的两点
if(dis[ly[j]]+s[j]<dis[lx[j]]){//
dis[lx[j]]=dis[ly[j]]+s[j];//
t=1;
}
}
if(!t)break;//如果没有边可以松弛,就可以直接退出
}
printf("%.2lf",dis[T]);
}