自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 21:25:21，当前版本为作者最后更新于2019-09-21 16:00:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

${\color{orange}\text{欢迎拜访我这个蒟蒻的博客}}$

P1462 【通往奥格瑞玛的道路】

此题算法:Dijkstra与他的二分

大致思路:

1.$$输入$i$站收费$f[i]$，求出二分范围$l$，起点和终点的费用最大值，和$r$，所有的城市收费最大值。

2.$$二分。只用不高于$mid$的收费站。二分条件：最少耗血是否小于最大血量。

3.$$输出答案$l$。

以下是代码加注释

#include<bits/stdc++.h>
using namespace std;
#define ong long long
const int N=10010;
const int M=100010;
const ong inf=LLONG_MAX/3;  //小心爆long long
int n,m,b,u,v;
int l,r,mid;
ong wi;  //爆int了
struct node{
	int a;
	ong dis;
};
bool operator < (node x,node y){
	return x.dis>y.dis; 
} priority_queue<node> q;
int top,g[N],f[N];
ong dis[N];
bool vis[N];
struct edge{
	int adj,nex;
	ong w;
}e[M];
void add(int x,int y,ong wor){
	e[++top]=(edge){y,g[x],wor}; 
	g[x]=top;
} void Dijkstra(int maxn){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
		vis[i]=0;
	} dis[1]=0;
	while(!q.empty()) q.pop();
	q.push((node){1,dis[1]});
	while(!q.empty()){
		node now=q.top(); q.pop();
		int x=now.a;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=g[x];i;i=e[i].nex){
			int p=e[i].adj;
			if(f[p]>maxn) continue;
			if(dis[x]+e[i].w<dis[p]){
				dis[p]=dis[x]+e[i].w;
				q.push((node){p,dis[p]});
			}
		}
	}
} int main(){
	scanf("%d%d%d",&n,&m,&b);
	for(int i=1;i<=n;i++){
		scanf("%d",f+i);
		r=max(r,f[i]);
	} l=max(f[1],f[n]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&wi);
		add(u,v,wi);
		add(v,u,wi);
	} while(l<r){
		mid=(l+r)>>1;
		Dijkstra(mid);
		if(dis[n]>b)
			l=mid+1;  //怕死循环
		else r=mid;
	} Dijkstra(l);
	if(dis[n]>b) printf("AFK\n");
	else printf("%d\n",l);
	return 0;
} 

最后我想说:我太蒟了！

谢谢大家! !