陆勤鑫爷

用户名：15073609987

访问量：2966

签　名：

聊胜于无

等　　级
排　　名	21957
经　　验	623
参赛次数	1
文章发表	7
年　　龄	20
在职情况	学生
学　　校
专　　业	军事物流

　　自我简介：

编程爱好者

TA的其他文章

蓝桥杯算法提高VIP-促销购物-题解(Java代码)
浏览：377

蓝桥杯算法提高VIP-种树-排序+搜索(C++代码)
浏览：465

蓝桥杯算法提高VIP-数的划分-题解(C++代码)
浏览：500

你可能喜欢

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

蓝桥杯算法提高VIP-道路和航路-SPFA+deque （C++代码）

　　作者: 陆勤鑫爷　　　　发表时间：2020-02-25 23:02:27 浏览：218　|　评论：1　

原题链接：蓝桥杯算法提高VIP-道路和航路

```cpp
include <cstdio>
include <cstring>
include <deque>
define MAX 150000
define INF 100000000
using namespace std ;
struct Node{
int to;//该边下一个节点
int w;//路程花费
int next;//所指向节点的下一个边
}edge[MAX];
int dis[MAX/4] , head[MAX/4] , c[MAX/4] ;
bool visited[MAX/4];
//因为节点数比较大，用SPFA算法和deque来优化
bool SPFA(int s , int n)
{
for(int i = 0 ; i <= n ; i++)
{
dis[i] = INF ;
c[i] = 0 ;
visited[i] = false ;
}
dis[s] = 0 ;
visited[s] = true ;
deque<int> que ;
que.push_front(s) ;//源点入队
while(!que.empty())
{
int k = que.front() ;//队顶点编号为k
que.pop_front() ;
visited[k] = false ;
c[k]++;
if(c[k]>n)
{
return false ;//判断负环
}
for(int i = head[k] ; i != -1 ; i = edge[i].next)
{
if(dis[edge[i].to] > dis[k]+edge[i].w)
{
dis[edge[i].to] = dis[k]+edge[i].w ;
if(que.empty())
{
que.push_front(edge[i].to) ;
visited[edge[i].to] = true ;
}
else if(!visited[edge[i].to])
{
if(dis[edge[i].to] > dis[que.front()])
{
que.push_back(edge[i].to) ;
}
else
{
que.push_front(edge[i].to) ;
}
visited[edge[i].to] = true ;
}
}
}
}
return true ;
}
int main()
{
int t,r,p,s;
scanf(“%d%d%d%d”,&t,&r,&p,&s)；
memset(head,-1,sizeof(head)) ;
int index = 0 ;
for(int i = 0 ; i < r; ++i)
{
int ai,bi,ci;
scanf(“%d%d%d”,&ai,&bi,&ci) ;
edge[index].to = bi ;
edge[index].w = ci ;
edge[index].next = head[ai] ;
head[ai] = index++ ;
edge[index].to = ai ;
edge[index].w = ci ;
edge[index].next = head[bi] ;
head[bi] = index++ ; //道路为双向
}
for(int i = 0 ; i < p ; ++i)
{
int ai,bi,ci;
scanf(“%d%d%d”,&ai,&bi,&ci) ;
edge[index].to = bi ;
edge[index].w = ci ;
edge[index].next = head[ai] ;
head[ai] = index++ ;//航路为单向
}
SPFA(s,t) ;//SPFA算法入口
for(int i = 1 ; i <= t ; ++i)
{
if(dis[i] == INF)
{
puts(“NO PATH”) ;
}
else
{
printf(“%d\n”,dis[i]) ;
}
}
}
return 0 ;
}
```

0.0分

2 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

石成仁

不仅编译错误，而且代码很耗时，不知道这样的代码贴出来用心何在？？

2020-05-21 18:11:18

陆勤鑫爷

TA的其他文章

你可能喜欢

汽水瓶（C++代码）

C语言考试练习题_一元二次方程（C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

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

蓝桥杯算法提高VIP-道路和航路-SPFA+deque （C++代码）

评论区

精彩推荐

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

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

【数组的距离】（C语言代码）

简单的for循环

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

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

1011题解

蚂蚁感冒（C语言代码）

sizeof的大作用（C语言代码）

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

陆勤鑫爷

TA的其他文章

你可能喜欢

汽水瓶 （C++代码）

C语言考试练习题_一元二次方程 （C语言代码）

汽水瓶 （C++代码）（直接n/2就可以了）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

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

蓝桥杯算法提高VIP-道路和航路-SPFA+deque （C++代码）

评论区

精彩推荐

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

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

【数组的距离】 （C语言代码）

简单的for循环

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

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

1011题解

蚂蚁感冒 （C语言代码）

sizeof的大作用 （C语言代码）

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

汽水瓶（C++代码）

C语言考试练习题_一元二次方程（C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

　　评论区

【数组的距离】（C语言代码）

蚂蚁感冒（C语言代码）

sizeof的大作用（C语言代码）

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