【C++】ZZ1530-[USACO10FEB]Chocolate Giving S 解题精讲
2022/6/5 1:20:28
本文主要是介绍【C++】ZZ1530-[USACO10FEB]Chocolate Giving S 解题精讲,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【Horn Coding Studio】CPP编程专栏(狄克斯特拉-算法)
题目
题目描述
Farmer John有B头奶牛(1<=B<=25000),有N(2\*B<=N<=50000)个农场,编号1-N,有M(N-1<=M<=100000)条双向边,第i条边连接农场R\_i和S\_i(1<=R\_i<=N;1<=S\_i<=N),该边的长度是L\_i(1<=L\_i<=2000)。居住在农场P\_i的奶牛A(1<=P\_i<=N),它想送一份新年礼物给居住在农场Q\_i(1<=Q\_i<=N)的奶牛B,但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物,然后再送给奶牛B。你的任务是:奶牛A至少需要走多远的路程?
输入
第一行:三个用空格隔开的整数N,M和B。
第二到M+1行:第i+1行用R_i,S_i和L_i三个用空格隔开的整数描述双向边i。
第M+2到M+B+1行:第M+i+1行包含两个用空格隔开的整数P_i和Q_i。
输出
第一到B行:第i行包括一个整数,居住在农场P_i的公牛从FJ那里取得情人节巧克力后送给他居住在农场Q_i的梦中情牛至少需要走的距离。
样例输入
6 7 3 1 2 3 5 4 3 3 1 1 6 1 9 3 4 2 1 4 4 3 2 2 2 4 5 1 3 6
样例输出
6 6 10
知识点普及
Dijkstra算法:详情请见算法介绍:Dijkstra 算法 - 冯子坤 - 博客园 (cnblogs.com)
一点即通
从今天起我们要使用一种新的算法,用来求最短路径问题,非常银杏,具体思路就是:让一只奶牛跑到FJ那边,然后再跑回p_i那里。细心的朋友都发现了,这样太慢!!!而且常量开这么大跑两遍确实非常勉强。
但是这数据有一点点水,水的亲妈都不认得那种。
进一步,我们发现,在第i头奶牛的行动中,肯定会经过1号点
所以,只要跑一边dijkstra就好了,把起点设为1
每当进行一次询问,就输出d[u]+d[v] ,复杂度不高,连cincout都能优秀的跑完。
代码
本次代码
ZZOJ 100%AC,25924KB空间复杂度,9MS优秀时间复杂度。
Luogu OJ 50%TLE,13789KB时间复杂度,1200MS超时
1 #include<bits/stdc++.h> 2 using namespace std ; 3 const int maxn = 1000001 ; 4 int n,m,t,k,s,e; 5 int dis[maxn], vis[maxn], head[maxn] ; 6 struct dy { 7 int x, y, z,next; 8 } a[maxn]; 9 void add(int x, int y, int z) { 10 a[t].x = x ; 11 a[t].y = y ; 12 a[t].z = z ; 13 a[t].next = head[x] ; 14 head[x] = t ++ ; 15 } 16 void dj(int s) { 17 queue<int>q ; 18 for(int i = 1 ; i <= n ; i ++) dis[i] = 1e9 ; 19 memset(vis, false, sizeof(vis)) ; 20 q.push(s) ; 21 dis[s] = 0 ; 22 while(!q.empty()) { 23 int u = q.front() ; 24 q.pop() ; 25 vis[u] = 0 ; 26 for(int i = head[u] ; i != -1 ; i = a[i].next ) { 27 int v = a[i].y ; 28 if(dis[v] > dis[u] + a[i].z) { 29 dis[v] = dis[u] + a[i].z ; 30 if(!vis[v]) { 31 vis[v] = true ; 32 q.push(v) ; 33 } 34 } 35 } 36 } 37 } 38 int p ; 39 int main() { 40 cin >> n >> m >> p ; 41 memset(head, -1, sizeof(head)) ; 42 while(m --) { 43 int x, y, z ; 44 cin >> x >> y >> z ; 45 add(x, y, z ) ; 46 add(y, x, z) ; 47 } 48 while( p --) { 49 cin >> s >> e ; 50 dj(s) ; 51 int w = dis[1] ; 52 dj(1) ; 53 cout << w + dis[e] <<endl; 54 } 55 } 56 /************************************************************** 57 User: FZK 58 Language: C++ 59 Result: 正确 60 Time:9 ms 61 Memory:29524 kb 62 ****************************************************************/View Code
笑一笑
这篇关于【C++】ZZ1530-[USACO10FEB]Chocolate Giving S 解题精讲的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升