洛谷P1462 通往奥格瑞玛的道路

二分费用。

用血量花费建图，用单源最短路判断 \(1\) 到 \(n\) 的最短路花费是否小于 \(b\) 。二分时需要不断记录合法的 \(mid\) 值。

这里建议使用while(l <= r)，会避免出现答案为 \(r\) 时和答案AFK搞混，样例就是这种情况。

复杂度为 \(O(\log n) \times\) 最短路的复杂度。

• 二分 + Dijkstra版本，复杂度为 \(O(\log n \times E\log E)\) 。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

const long long inf = 1e9+7;

const int maxn = 10005;

const int maxm = 50005;

int n, m, l, r, ai, bi, tot, head[maxn], vis[maxn], f[maxn];

long long b, ci, dist[maxn];

struct node{

    int to, nex;

    long long cost;

}edge[2 * maxm];

struct G{

    int id;

    long long cost;

    G(){}

    G(int _id, long long _cost){

        id = _id; cost = _cost;

    }

    /******/

    bool operator < (const G & _G) const {

        return cost > _G.cost;

    }

}now;

inline void addedge(int u, int v, long long w){

    edge[++tot].to = v;

    edge[tot].cost = w;

    edge[tot].nex = head[u];

    head[u] = tot;

}

int dijkstra(int c)

{

    for(int i = 1; i <= n; i++) vis[i] = 0, dist[i] = inf;

    priority_queue<G> q;

    while(!q.empty()) q.pop();

    q.push(G(1, 0));

    dist[1] = 0;

    while(!q.empty()){

        now = q.top(); q.pop();

        if(vis[now.id] == 1) continue;

        vis[now.id] = 1;

        for(int j = head[now.id]; j > 0; j = edge[j].nex){

            int tmp = edge[j].to;

            if(vis[tmp] == 0 && dist[tmp] > dist[now.id] + edge[j].cost && f[tmp] <= c){

                dist[tmp] = dist[now.id] + edge[j].cost;

                q.push(G(tmp, dist[tmp]));

            }

        }

    }

    if(dist[n] < b) return 1;

    else return 0;

}

int main()

{

    scanf("%d%d%lld", &n, &m, &b);

    for(int i = 1; i <= n; i++){

        scanf("%d", &f[i]);

        r = max(r, f[i]);

    }

    for(int i = 1; i <= m; i++){

        scanf("%d%d%lld", &ai, &bi, &ci);

        addedge(ai, bi, ci);

        addedge(bi, ai, ci);

    }

    int ans = 0;

    while(l <= r){

        int mid = (l + r) >> 1;

        if(dijkstra(mid)) ans = mid, r = mid - 1;

        else l = mid + 1;

    }

    if(ans == 0) printf("AFK\n");

    else printf("%d\n", ans);

    return 0;

}

• 二分 + spfa版本，复杂度为 \(O(\log n \times kE)\) ，\(k\) 通常为 \(2\) 。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

const long long inf = 1e9+7;

const int maxn = 10005;

const int maxm = 50005;

int n, m, l, r, ai, bi, tot, head[maxn], vis[maxn], f[maxn];

long long b, ci, dist[maxn];

struct node{

    int to, nex;

    long long cost;

}edge[2 * maxm];

queue<int> q;

inline void addedge(int u, int v, long long w){

    edge[++tot].to = v;

    edge[tot].cost = w;

    edge[tot].nex = head[u];

    head[u] = tot;

}

int spfa(int c){

    for(int i = 1; i <= n; i++) dist[i] = inf, vis[i] = 0;

    q.push(1); vis[1] = 1; dist[1] = 0;

    while(!q.empty()){

        int now = q.front();

        q.pop();

        vis[now] = 0;

        for(int i = head[now]; i > 0; i = edge[i].nex){

            int v = edge[i].to;

            if(dist[v] > dist[now] + edge[i].cost && f[v] <= c){

                dist[v] = dist[now] + edge[i].cost;

                if(vis[v] == 0){

                    /******/

                    vis[v] = 1;

                    q.push(v);

                }

            }

        }

    }

    if(dist[n] < b) return 1;

    else return 0;

}

int main()

{

    scanf("%d%d%lld", &n, &m, &b);

    for(int i = 1; i <= n; i++){

        scanf("%d", &f[i]);

        r = max(r, f[i]);

    }

    for(int i = 1; i <= m; i++){

        scanf("%d%d%lld", &ai, &bi, &ci);

        addedge(ai, bi, ci);

        addedge(bi, ai, ci);

    }

    int ans = 0;

    while(l <= r){

        int mid = (l + r) >> 1;

        if(spfa(mid)) ans = mid, r = mid - 1;

        else l = mid + 1;

    }

    if(ans == 0) printf("AFK\n");

    else printf("%d\n", ans);

    return 0;

}