陆勤鑫爷

用户名：15073609987

访问量：3248

签　名：

聊胜于无

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

　　自我简介：

编程爱好者

TA的其他文章

蓝桥杯2013年第四届真题-格子刷油漆-DFS(C++代码)
浏览：743

你可能喜欢

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

　　作者: 陆勤鑫爷　　　　发表时间：2020-02-25 23:02:27 浏览：245　|　评论：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语言程序设计教程（第三版）课后习题7.1 （C语言代码）

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

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

Tom数（C语言代码）

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

C语言训练-求PI* （C语言代码）

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

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

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

水仙花（C语言代码）

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

核桃的数量（C语言代码）

交换Easy （C语言代码）

陶陶摘苹果2 （C语言代码）

陆勤鑫爷

TA的其他文章

你可能喜欢

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

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

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

Tom数 （C语言代码）

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

C语言训练-求PI* （C语言代码）

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

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

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

水仙花 （C语言代码）

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

核桃的数量 （C语言代码）

交换Easy （C语言代码）

陶陶摘苹果2 （C语言代码）

Tom数（C语言代码）

　　评论区

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

水仙花（C语言代码）

核桃的数量（C语言代码）