首页 > 代码库 > 通往奥格瑞玛的道路（洛谷 1462）
通往奥格瑞玛的道路（洛谷 1462）
题目背景
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量 有一天他醒来后发现自己居然到了联盟的主城暴风城 在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛
题目描述
在艾泽拉斯，有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。
输入输出样例
输入样例#1：
4 4 8856102 1 22 4 11 3 43 4 3
输出样例#1：
10
说明
对于60%的数据，满足n≤200，m≤10000，b≤200
对于100%的数据，满足n≤10000，m≤50000，b≤1000000000
对于100%的数据，满足ci≤1000000000，fi≤1000000000，可能有两条边连接着相同的城市。
/* 二分答案+spfa 水过 二分出答案后，看从1到n的最少血量是否小于b，在spfa的过程中注意只有费用小于或等于 二分出的答案，才能更新最短路。 */#include<cstdio>#include<iostream>#include<cstring>#define N 10010#define M 50010using namespace std;int first[N],mon[N],dis[N],q[N*4],vis[N],n,m,b;struct node{ int v,pre,t;};node e[M*2];int read(){ char c=getchar();int num=0,flag=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)flag=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*flag;}void add(int i,int x,int y,int z){ e[i].v=y; e[i].t=z; e[i].pre=first[x]; first[x]=i;}bool check(int limit){ memset(dis,0x3f3f3f3f,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(q,0,sizeof(q)); int head=0,tail=1; dis[1]=0; q[1]=1; vis[1]=1; while(head<tail) { int x=q[++head]; vis[x]=0; for(int i=first[x];i;i=e[i].pre) if(dis[x]+e[i].t<dis[e[i].v]&&mon[e[i].v]<=limit) { dis[e[i].v]=dis[x]+e[i].t; if(!vis[e[i].v]) { vis[e[i].v]=1; q[++tail]=e[i].v; } } } if(dis[n]<b)return true; return false;}int main(){ int l=0,r=0; n=read();m=read();b=read(); for(int i=1;i<=n;i++) mon[i]=read(),r=max(r,mon[i]); l=mon[1]; for(int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); add(i*2-1,x,y,z);add(i*2,y,x,z); } while(l<=r) { int mid=(l+r)/2; if(check(mid))r=mid-1; else l=mid+1; } if(check(l))printf("%d",l); else printf("AFK"); return 0;}
通往奥格瑞玛的道路（洛谷 1462）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。