P1462 通往奥格瑞玛的道路
2018-06-17 22:24:49来源:未知 阅读 ()
题目背景
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士,他是部落的中坚力量
有一天他醒来后发现自己居然到了联盟的主城暴风城
在被众多联盟的士兵攻击后,他决定逃回自己的家乡奥格瑞玛
题目描述
在艾泽拉斯,有n个城市。编号为1,2,3,...,n。
城市之间有m条双向的公路,连接着两个城市,从某个城市到另一个城市,会遭到联盟的攻击,进而损失一定的血量。
每次经过一个城市,都会被收取一定的过路费(包括起点和终点)。路上并没有收费站。
假设1为暴风城,n为奥格瑞玛,而他的血量最多为b,出发时他的血量是满的。
歪嘴哦不希望花很多钱,他想知道,在可以到达奥格瑞玛的情况下,他所经过的所有城市中最多的一次收取的费用的最小值是多少。
输入输出格式
输入格式:第一行3个正整数,n,m,b。分别表示有n个城市,m条公路,歪嘴哦的血量为b。
接下来有n行,每行1个正整数,fi。表示经过城市i,需要交费fi元。
再接下来有m行,每行3个正整数,ai,bi,ci(1<=ai,bi<=n)。表示城市ai和城市bi之间有一条公路,如果从城市ai到城市bi,或者从城市bi到城市ai,会损失ci的血量。
输出格式:仅一个整数,表示歪嘴哦交费最多的一次的最小值。
如果他无法到达奥格瑞玛,输出AFK。
输入输出样例
4 4 8 8 5 6 10 2 1 2 2 4 1 1 3 4 3 4 3
10
说明
对于60%的数据,满足n≤200,m≤10000,b≤200
对于100%的数据,满足n≤10000,m≤50000,b≤1000000000
对于100%的数据,满足ci≤1000000000,fi≤1000000000,可能有两条边连接着相同的城市。
二分答案+SPFA
注意要开long long 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #define lli long long int 7 using namespace std; 8 void read(lli & n) 9 { 10 char c='+';lli x=0; 11 while(c<'0'||c>'9') 12 c=getchar(); 13 while(c>='0'&&c<='9') 14 { 15 x=x*10+(c-48); 16 c=getchar(); 17 } 18 n=x; 19 } 20 const lli MAXN=100001; 21 const lli maxn=0x7fffffff; 22 struct node 23 { 24 lli u,v,w,nxt; 25 }edge[MAXN]; 26 lli head[MAXN]; 27 lli num=1; 28 lli dis[MAXN]; 29 lli vis[MAXN]; 30 lli n,m,maxnblood; 31 lli spend[MAXN]; 32 lli l=0x7fffffff,r=-1; 33 void add_edge(lli x,lli y,lli z) 34 { 35 edge[num].u=x; 36 edge[num].v=y; 37 edge[num].w=z; 38 edge[num].nxt=head[x]; 39 head[x]=num++; 40 } 41 lli SPFA(lli r) 42 { 43 if(r<spend[1]) 44 {return 0;} 45 for(lli i=1;i<=n+1;i++) 46 dis[i]=maxn,vis[i]=0; 47 queue<int>q; 48 q.push(1); 49 vis[1]=1; 50 dis[1]=0; 51 while(q.size()!=0) 52 { 53 lli p=q.front(); 54 q.pop(); 55 vis[p]=0; 56 for(lli i=head[p];i!=-1;i=edge[i].nxt) 57 { 58 lli will=edge[i].v; 59 if((dis[will]>dis[p]+edge[i].w)&&spend[will]<=r) 60 { 61 dis[will]=dis[p]+edge[i].w; 62 if(vis[will]==0) 63 { 64 vis[will]=1; 65 q.push(will); 66 } 67 } 68 } 69 } 70 if(dis[n]<=maxnblood) 71 return 1; 72 else 73 return 0; 74 } 75 int main() 76 { 77 read(n);read(m);read(maxnblood); 78 for(lli i=1;i<=n;i++) 79 head[i]=-1; 80 for(lli i=1;i<=n;i++) 81 { 82 read(spend[i]); 83 l=min(spend[i],l); 84 r=max(spend[i],r); 85 } 86 for(lli i=1;i<=m;i++) 87 { 88 lli x,y,z; 89 read(x);read(y);read(z); 90 add_edge(x,y,z); 91 add_edge(y,x,z); 92 } 93 lli ans=0; 94 while(l<=r) 95 { 96 lli mid=(l+r)/2; 97 if(SPFA(mid)) 98 { 99 ans=mid; 100 r=mid-1; 101 } 102 else l=mid+1; 103 } 104 //printf("%d",r); 105 if(ans&&SPFA(ans)) 106 printf("%d",ans); 107 else 108 printf("AFK"); 109 return 0; 110 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash