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

· · 题解

{\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;
}

最后我想说:我太蒟了！

谢谢大家! !