一本通1342:【例4-1】最短路径问题

1342:【例4-1】最短路径问题


时间限制: 1000 ms         内存限制: 65536 KB
提交数: 14493     通过数: 6553

【题目描述】

平面上有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

代码如下,采用Floyed的算法 O(n*n*n) 用的是快读,还呈上没有快读的代码。感觉没什么区别,甚至还慢一点!!!

#include<cstdio>
#include<cmath>
#include<cstring>
int point[300][3];
double map[300][300];
inline int read(){
	int res=0;
	int f=1;
	char c=getchar();
	while(c<'0'|| c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0' && c<='9'){
		res=(res<<1)+(res<<3)+(c^48);
		c=getchar();
	}
	return res*f;
}
int main(){
	memset(map,0x7f,sizeof(map));
	int v,e;
	v=read();
	for(int i=1;i<=v;i++){
		point[i][1]=read();
		point[i][2]=read();
	}
	e=read();
	int x1,x2;
	double res;
	int start,end;
	for(int i=1;i<=e;i++){
		x1=read();
		x2=read();
		res=sqrt(double(pow((point[x1][1]-point[x2][1]),2))+double(pow((point[x1][2]-point[x2][2]),2)));
		map[x1][x2]=res;
		map[x2][x1]=res;
	}
	start=read();
	end=read();
	for(int k=1;k<=v;k++){
		for(int i=1;i<=v;i++){
			for(int j=1;j<=v;j++){
				if(i!=k &&j!=k &&i!=j && map[i][j]>map[i][k]+map[k][j]){
					map[i][j]=map[i][k]+map[k][j];
				}
			}
		}
	}
	printf("%.2lf",map[start][end]);
	return 0;
}

测试结果:

程序运行结果


用户名:MaryL,题目编号:1342,运行编号:12792602,代码长度:1007Bytes

通过
 

测试点 结果 内存 时间
测试点1 答案正确 1004KB 5MS
测试点2 答案正确 1004KB 6MS
测试点3 答案正确 996KB 4MS
测试点4 答案正确 996KB 8MS
测试点5 答案正确 996KB 8MS

没有快读:

#include<cstdio>
#include<cmath>
#include<cstring>
int point[300][3];
double map[300][300];
int main(){
	memset(map,0x7f,sizeof(map));
	int v,e;
	scanf("%d",&v);
	for(int i=1;i<=v;i++){
		scanf("%d %d",&point[i][1],&point[i][2]);
	}
	scanf("%d",&e);
	int x1,x2;
	double res;
	int start;
	int end;
	for(int i=1;i<=e;i++){
		scanf("%d %d",&x1,&x2);
		res=sqrt(double(pow((point[x1][1]-point[x2][1]),2))+double(pow((point[x1][2]-point[x2][2]),2)));
		map[x1][x2]=res;
		map[x2][x1]=res;
	}
	scanf("%d %d",&start,&end);
	for(int k=1;k<=v;k++){
		for(int i=1;i<=v;i++){
			for(int j=1;j<=v;j++){
				if(i!=j&& i!=k&& j!=k &&map[i][j]>map[i][k]+map[k][j]){
					map[i][j]=map[i][k]+map[k][j];
				}
			}
		}
	}
	printf("%.2lf",map[start][end]);
	return 0;
}

测试结果:

程序运行结果


用户名:MaryL,题目编号:1342,运行编号:12792646,代码长度:786Bytes

通过
 

测试点 结果 内存 时间
测试点1 答案正确 1004KB 3MS
测试点2 答案正确 1004KB 6MS
测试点3 答案正确 1004KB 6MS
测试点4 答案正确 1008KB 7MS
测试点5 答案正确 1008KB 6MS
上一篇:java中的构造块、静态块等说明


下一篇:LeetCode-Python-1342. 数组大小减半(贪心 + 堆)