少年Q

用户名：yin19990129

访问量：25370

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

40.殊途同归（C++代码）只做最好的思路！
浏览：508

41.输出全排列-题解(C++代码)只做最好的思路！
浏览：882

42.x皇后问题（C++代码）只做最好的思路！
浏览：336

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

等待戈多-题解（C++代码）只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-05-09 11:31:40 浏览：333　|　评论：0　

原题链接：等待戈多

这题本质上考察的是单源最短路径加上一个时间属性的问题，由于需要对速度属性进行判定并且还要考虑自环可能性的验证，所以这里采用spfa算法来进行松弛，并求出最短路径。具体代码如下：
```cpp
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue> 
using namespace std;
const int maxn=505;
const int inf=1e9;
int n,k;
double e[maxn][maxn];//注意要用double的邻接矩阵
bool vis[maxn];//判重数组
double dis[maxn];//double距离数组
//初始化距离数组 
void init(){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
	}
}
//spfa核心代码（模板）
void spfa(){
	init();//初始化
	queue<int>q;
	dis[1]=0;//从1号结点开始，距离为0
	q.push(1);
	while(!q.empty()){
		int now=q.front();
		vis[now]=false;
		q.pop();
		for(int i=1;i<=n;i++){
			//注意处理自环的边
		    if(now!=i&&dis[i]>dis[now]+e[now][i]){
		    	dis[i]=dis[now]+e[now][i];//松弛操作 
		    	if(!vis[i]){
		    		vis[i]=true;
		    		q.push(i);
		    	}
		    }
		}
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%lf",&e[i][j]);//先读入路程 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int val;
			scanf("%d",&val);
			if(!val){
				e[i][j]=inf;//如果速度为0，就代表着自环或无法到达，权值给它个inf
			}else{
				e[i][j]/=val;//时间=路程/速度
			}
		}
	}
	spfa();
	printf("%.2lf",dis[k]);//1~k的距离就是d[k]
	return 0;
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

少年Q

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-计负均正（C语言代码）

等待戈多-题解（C++代码）只做最好的思路！

评论区

精彩推荐

人民币问题（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

DNA （C++代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

【计算两点间的距离】（C语言代码）

兰顿蚂蚁（C++代码）

少年Q

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-计负均正 （C语言代码）

等待戈多-题解（C++代码）只做最好的思路！

评论区

精彩推荐

人民币问题 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

DNA （C++代码）

【绝对值排序】 （C++代码）（利用两个库函数——abs()求绝对值 和 sort()快排）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

【计算两点间的距离】 （C语言代码）

兰顿蚂蚁 （C++代码）

C二级辅导-计负均正（C语言代码）

　　评论区

人民币问题（C语言代码）

C二级辅导-进制转换（C语言代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

【计算两点间的距离】（C语言代码）

兰顿蚂蚁（C++代码）