BZOJ 2100 Usaco2010 Dec Apple Delivery
时间:2022-03-13 20:09
2100: [Usaco2010 Dec]Apple Delivery
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 894 Solved: 348
[][][]
Description
Bessie has two crisp red apples to deliver to two of her friends in the herd. Of course, she travels the C (1 <= C <= 200,000) cowpaths which are arranged as the usual graph which connects P (1 <= P <= 100,000) pastures conveniently numbered from 1..P: no cowpath leads from a pasture to itself, cowpaths are bidirectional, each cowpath has an associated distance, and, best of all, it is always possible to get from any pasture to any other pasture. Each cowpath connects two differing pastures P1_i (1 <= P1_i <= P) and P2_i (1 <= P2_i <= P) with a distance between them of D_i. The sum of all the distances D_i does not exceed 2,000,000,000. What is the minimum total distance Bessie must travel to deliver both apples by starting at pasture PB (1 <= PB <= P) and visiting pastures PA1 (1 <= PA1 <= P) and PA2 (1 <= PA2 <= P) in any order. All three of these pastures are distinct, of course. Consider this map of bracketed pasture numbers and cowpaths with distances: If Bessie starts at pasture [5] and delivers apples to pastures [1] and [4], her best path is: 5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1* with a total distance of 12.
一张P个点的无向图,C条正权路。CLJ要从Pb点(家)出发,既要去Pa1点NOI赛场拿金牌,也要去Pa2点CMO赛场拿金牌。(途中不必回家)
可以先去NOI,也可以先去CMO。
当然神犇CLJ肯定会使总路程最小,输出最小值。
Input
* Line 1: Line 1 contains five space-separated integers: C, P, PB, PA1, and PA2 * Lines 2..C+1: Line i+1 describes cowpath i by naming two pastures it connects and the distance between them: P1_i, P2_i, D_i
Output
* Line 1: The shortest distance Bessie must travel to deliver both apples
Sample Input
9 7 5 1 45 1 7
6 7 2
4 7 2
5 6 1
5 2 4
4 3 2
1 2 3
3 2 2
2 6 3
Sample Output
12HINT
求翻译.........站内PM我吧.........
Source
因为图是无向图,所以做两次spfa,分别以pa1和pa2为起点即可
1 #include <bits/stdc++.h> 2 #define ll long long 3 #define inf 1000000 4 #define eps 1e-7 5 using namespace std; 6 inline int read(){ 7 int x=0;int f=1;char ch=getchar(); 8 while(!isdigit(ch)) {if(ch==‘-‘) f=-1;ch=getchar();} 9 while(isdigit(ch)) {x=x*10+ch-‘0‘;ch=getchar();} 10 return x*f; 11 } 12 const int MAXN=1e6+10; 13 struct node{ 14 int y,next,v; 15 }e[MAXN]; 16 int linkk[MAXN],len,n,m,dis[MAXN],vis[MAXN]; 17 inline void insert(int xx,int yy,int vv){ 18 e[++len].y=yy;e[len].next=linkk[xx];e[len].v=vv;linkk[xx]=len; 19 } 20 void spfa(int st){ 21 deque < int > q; 22 memset(dis,10,sizeof(dis)); 23 memset(vis,0,sizeof(vis)); 24 q.push_back(st);dis[st]=0;vis[st]=1; 25 while(!q.empty()){ 26 int tn=q.front();q.pop_front();vis[tn]=0; 27 for(int i=linkk[tn];i;i=e[i].next){ 28 if(dis[e[i].y]>dis[tn]+e[i].v){ 29 dis[e[i].y]=dis[tn]+e[i].v; 30 if(!vis[e[i].y]){ 31 vis[e[i].y]=1; 32 if(!q.empty()&&dis[q.front()]>dis[e[i].y]) q.push_front(e[i].y); 33 else q.push_back(e[i].y); 34 } 35 } 36 } 37 } 38 } 39 int main(){ 40 m=read();n=read();int s=read();int t1=read();int t2=read(); 41 for(int i=1;i<=m;i++){ 42 int xx=read();int yy=read();int vv=read();; 43 insert(xx,yy,vv);insert(yy,xx,vv); 44 } 45 spfa(t1); 46 int ans=dis[t2]+dis[s]; 47 spfa(t2); 48 ans=min(ans,dis[t1]+dis[s]); 49 cout<<ans<<endl; 50 return 0; 51 }View Code
相关推荐
- Android系统编程入门系列之界面Activity交互响应
- 新型横向移动工具原理分析、代码分析、优缺点以及检测方案
- uni-app滚动视图容器(scroll-view)之监听上拉事件
- uniapp h5,app两端复制文本
- Android系统编程入门系列之界面Activity响应丝滑的传统动画
- 【Azure 应用服务】App Service 配置 Application Settings 访问Storage Account得到 could not be resolved: '*.file.core.windows.net'的报错。没有解析成对应中国区 Storage Account地址 *.file.core.chinacloudapi.cn
- 诺基亚短信生成!太好玩了
- iOS 跳转App Store进行评分
- 开发一个即时通讯App
- 关闭苹果IOS app自动更新
电脑软件
本类排行
- 1关闭苹果IOS app自动更新
- 2iOS 跳转App Store进行评分
- 3诺基亚短信生成!太好玩了
- 4Android系统编程入门系列之界面Activity响应丝滑的传统动画
- 5uniapp h5,app两端复制文本
- 6uni-app滚动视图容器(scroll-view)之监听上拉事件
- 7新型横向移动工具原理分析、代码分析、优缺点以及检测方案
- 8Android系统编程入门系列之界面Activity交互响应
- 9开发一个即时通讯App
- 10【Azure 应用服务】App Service 配置 Application Settings 访问Storage Account得到 could not be resolved: '*.file.core.windows.net'的报错。没有解析成对应中国区 Storage Account地址 *.file.core.chinacloudapi.cn