计蒜客 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

相关文章

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

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the