计蒜客 Magical Girl Haze ——dijkstra+优先队列

2024-04-07 01:08

本文主要是介绍计蒜客 Magical Girl Haze ——dijkstra+优先队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

There are NN cities in the country, and MM directional roads from uu to v(1\le u, v\le n)v(1≤u,v≤n). Every road has a distance c_ic
i
​ . Haze is a Magical Girl that lives in City 11, she can choose no more than KK roads and make their distances become 00. Now she wants to go to City NN, please help her calculate the minimum distance.

Input
The first line has one integer T(1 \le T\le 5)T(1≤T≤5), then following TT cases.

For each test case, the first line has three integers N, MN,M and KK.

Then the following MM lines each line has three integers, describe a road, U_i, V_i, C_iU
i
​ ,V
i
​ ,C
i
​ . There might be multiple edges between uu and vv.

It is guaranteed that N \le 100000, M \le 200000, K \le 10N≤100000,M≤200000,K≤10,
0 \le C_i \le 1e90≤C
i
​ ≤1e9. There is at least one path between City 11 and City NN.

Output
For each test case, print the minimum distance.

样例输入 复制
1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2
样例输出 复制
3
题目来源
ACM-ICPC 2018 南京赛区网络预赛

当时比赛的时候用dp+dij的,但是由于我处理顺序写的比较失败这道题卡了好久,还是队友写了个暴力才过的。
只需要用一个dij就好了,优先队列重载一下操作符就像上次那道做公交车换乘的题目一样,真是失误

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
#define ll long long
const int maxn=1e5+5;
const ll inf=1e17;
struct edge
{int to,next;ll val;
}e[maxn*2];
int head[maxn],cnt;
void add(int x,int y,ll w)
{e[cnt].to=y;e[cnt].val=w;e[cnt].next=head[x];head[x]=cnt++;
}
ll dist[maxn][11],vis[maxn][11];
struct node
{ll dis;int num,pos;node(){}node(ll dis,int num,int pos):dis(dis),num(num),pos(pos){}bool operator< (const node& a)const{if(dis==a.dis)return num>a.num;return dis>a.dis;}
};
int n,m,k;
void dijkstra()
{priority_queue<node>Q;Q.push(node(0,0,1));while(!Q.empty()){node v=Q.top();Q.pop();if(vis[v.pos][v.num])continue;vis[v.pos][v.num]=1;for(int i=head[v.pos];~i;i=e[i].next){int ne=e[i].to;if(dist[ne][v.num]>v.dis+e[i].val){dist[ne][v.num]=v.dis+e[i].val;Q.push(node(dist[ne][v.num],v.num,ne));}if(v.num<k&&v.dis<dist[ne][v.num+1]){dist[ne][v.num+1]=v.dis;Q.push(node(v.dis,v.num+1,ne));}}}
}
void init()
{for(int i=0;i<maxn;i++){head[i]=-1;for(int j=0;j<=10;j++)dist[i][j]=inf,vis[i][j]=0;}cnt=0;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&k);int x,y;ll val;init();for(int i=1;i<=m;i++){scanf("%d%d%lld",&x,&y,&val);add(x,y,val);}for(int i=0;i<=k;i++)dist[1][0]=0;dijkstra();ll ans=inf;for(int i=0;i<=k;i++)ans=min(ans,dist[n][i]);printf("%lld\n",ans);}return 0;
}

这篇关于计蒜客 Magical Girl Haze ——dijkstra+优先队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881294

相关文章

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

uva 10801(乘电梯dijkstra)

题意: 给几个电梯,电梯0 ~ n-1分别可以到达很多层楼。 换乘电梯需要60s时间。 问从0层到target层最小的时间。 解析: 将进入第0层的电梯60s也算上,最后减。 坑点是如果target为0输出0。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algori

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 3255 次短路(第k短路) A* + spfa 或 dijkstra

题意: 给一张无向图,求从1到n的次短路。 解析: A* + spfa 或者 dijkstra。 详解见上一题:http://blog.csdn.net/u013508213/article/details/46400189 本题,spfa中,stack超时,queue的效率最高,priority_queue次之。 代码: #include <iostream>#i