通往奥格瑞玛的道路

题目背景

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。

有一天他醒来后发现自己居然到了联盟的主城暴风城。

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。

题目描述

在艾泽拉斯，有 \(n\) 个城市。编号为 \(1,2,3,\ldots,n\)。

城市之间有 \(m\) 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设 \(1\) 为暴风城，\(n\) 为奥格瑞玛，而他的血量最多为 \(b\)，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

输入格式

第一行 \(3\) 个正整数，\(n,m,b\)。分别表示有 \(n\) 个城市，\(m\) 条公路，歪嘴哦的血量为 \(b\)。

接下来有 \(n\) 行，每行 \(1\) 个正整数，\(f_i\)。表示经过城市 \(i\)，需要交费 \(f_i\) 元。

再接下来有 \(m\) 行，每行 \(3\) 个正整数，\(a_i,b_i,c_i\)（\(1\leq a_i,b_i\leq n\)）。表示城市 \(a_i\) 和城市 \(b_i\) 之间有一条公路，如果从城市 \(a_i\) 到城市 \(b_i\)，或者从城市 \(b_i\) 到城市 \(a_i\)，会损失 \(c_i\) 的血量。

输出格式

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出 AFK。

样例 #1

样例输入 #1

4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

样例输出 #1

10

提示

对于 \(60\%\) 的数据，满足 \(n\leq 200\)，\(m\leq 10^4\)，\(b\leq 200\)；

对于 \(100\%\) 的数据，满足 \(n\leq 10^4\)，\(m\leq 5\times 10^4\)，\(b\leq 10^9\)；

对于 \(100\%\) 的数据，满足 \(c_i\leq 10^9\)，\(f_i\leq 10^9\)，可能有两条边连接着相同的城市。

分析

• 法1：既然要求最大费用的最小值，考虑把所有最大费用找出来，求最小，dfs/bfs，可能TLE。

• 法2：二分答案，spfa或者dijkstra求最短路，检查费用不超过mid的情况下能否到 n。

• bfs，这个程序很奇怪呀，按理会TLE，但是没有，反而WA了，待调

• spfa/pri_dijkstr，wa一个点，奇怪

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10,INF=0x3f3f3f3f;
int n,m,b,f[N],head[N],cnt=0,mx[N],pmx=0,vis[N],ans=INF;
struct T {
    int to,nxt; LL w;
    T(int a=0,LL b=0,int c=0):to(a),w(b),nxt(c) {}
    bool operator< (const T& rhs) const {
        return w > rhs.w;
    }
} G[N], p;
void add(int u,int v,int w) {
    G[++cnt].to=v;
    G[cnt].w=w, G[cnt].nxt=head[u];
    head[u]=cnt;
}

void bfs() {// 1->n 预计 TLE，无需 LL
    queue<T> que;
    que.push(T(1, b, f[1])), vis[1]=1;
    while(que.size()) {
        p = que.front(), que.pop();
        if(p.to==n) {
            ans=min(ans,p.nxt); continue;
        }
        int u=p.to, v, w, mf; vis[u]=1;
        for(int i=head[u]; ~i; i=G[i].nxt) {
            v=G[i].to, w=G[i].w, mf=max(f[v], p.nxt);
            if(p.w >= w && !vis[v]) {
                que.push(T(v,p.w-w,mf));
            }
        }
    }
}

LL dis[N];
// 最大费用不超过mid的情况下能否到 n
bool spfa(int mid) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0x00, sizeof(vis));
    queue<int> que;
    que.push(1), dis[1]=0, vis[1]=1;
    while(que.size()) {
        int u=que.front(); que.pop(), vis[u]=0;
        for(int i=head[u]; ~i; i=G[i].nxt) {
            int v=G[i].to, w=G[i].w;
            if(dis[v] > dis[u]+w && f[v]<=mid) {
                dis[v] = dis[u]+w;
                if(!vis[v]) que.push(v), vis[v]=1;
            }
        }
    }
    return dis[n]<=b;
}
bool pri_dijkstra(int mid) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0x00, sizeof(vis));
    priority_queue<T> que;
    que.push(T(1,0)), dis[1]=0;
    while(que.size()) {
        int u=que.top().to; que.pop();
        if(vis[u]) continue; vis[u]=1;
        for(int i=head[u]; ~i; i=G[i].nxt) {
            LL v=G[i].to, w=G[i].w;
            if(dis[v] > dis[u]+w && f[v]<=mid) {
                dis[v] = dis[u]+w;
                que.push(T(v,dis[v]));
            }
        }
    }
    return dis[n]<=b;
}
int main() {
    freopen("data.in", "r", stdin);
    memset(head,-1,sizeof(head));
    scanf("%d%d%d", &n,&m,&b);
    for(int i=1; i<=n; i++) scanf("%d", &f[i]);
    int u,v,w;
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d",&u,&v,&w), add(u,v,w), add(v,u,w);
    }
//    bfs();
    int l=1, r=-1;
    for(int i=1; i<=n; i++) r=max(r,f[i]);
    while(l<=r) {
        int mid=(l+r)/2;
        if(spfa(mid)) ans=mid,r=mid-1;
//        if(pri_dijkstra(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans==INF) printf("AFK\n");
    else printf("%d\n",ans);
    return 0;
}

原文地址：http://www.cnblogs.com/hellohebin/p/16790290.html