(luogu1462)通往奥格瑞玛的道路

发表于 | 分类于 ，

题目描述:

从结点1出发, 到结点n(n<=10000), 一共有m(m<=50000)条双向的道路, 给出每个点的权值, 以及初始血量, 求最大权值的最小值(无解输出”AFK”)

思路;

最短路+二分答案

求解极值考虑使用二分答案

对权值进行二分搜索, 用dijkstra求最少血量损失, 求最短路时去掉比权值大的点.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int Mn(10005);
const int Mm(100005);
struct edge
{
    int e,c,next;
}E[Mm]; //边表
int n,hp; //结点数及血量上限
int v[Mn];
int f[Mn];
long long dc[Mn];
bool isd[Mn];
struct node
{
    int u,d;
    bool operator <(const node& x) const
    {
        return d>x.d;
    }
};
bool dij(int d) //堆优化dijkstra
{
    memset(dc,0x3f,sizeof dc);
    memset(isd,0,sizeof isd);
    dc[1] = 0;
    priority_queue<node> pq;
    pq.push((node){1,dc[1]});
    while(!pq.empty())
    {
        int np(pq.top().u);
        pq.pop();
        if(!isd[np])
        {
            if(np==n)
            {
                if(dc[np]<hp)	return true;
                else	return false; //如果最小损失血量大于血量上限, 答案不可行
            }
            isd[np] = true;
            for(int e(v[np]);e;e=E[e].next)
            {
                if(f[E[e].e]<=d && dc[E[e].e]>dc[np]+E[e].c)
                {
                    dc[E[e].e] = dc[np]+E[e].c;
                    pq.push((node){E[e].e,dc[E[e].e]});
                }
            }
        }
    }
    return false;
}
int main()
{
    int m;
    cin >> n >> m >> hp;
    int mf(0); //所有结点的最大权值
    for(int i(1);i<=n;++i)
    {
        scanf("%d",f+i);
        mf = max(mf,f[i]);
    }
    int cnt(0);
    while(m--)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        E[++cnt].e=b, E[cnt].c=c, E[cnt].next=v[a];
        v[a] = cnt;
        E[++cnt].e=a, E[cnt].c=c, E[cnt].next=v[b];
        v[b] = cnt;
    }
    if(!dij(mf)) //先判断在最大权值下是否能够到达
        cout << "AFK";
    else
    {
        int l(0),r(mf);
        while(l<r) //二分答案
        {
            int mid((l+r)>>1);
            if(dij(mid))	r=mid;
            else	l=mid+1;
        }
        cout << l;
    }
    return 0;
}