【NOI导刊200908模拟试题02 题4】【二分+Dijkstra】收费站

Description

　　在某个遥远的国家里，有n个城市。编号外1,2,3，…，n。
　　这个国家的政府修建了m条双向的通路。每条公路连接着两个城市。沿着某条公路，开车从一个城市到另一个城市，需要花费一定的汽油。
　　开车每经过一个城市，都会被收取一定的费用（包括起点和终点城市）。所有的收费站都在城市中，在城市间的公路上没有任何收费站。
　　小红现在要开车从城市u到城市v（1<=u,v<=n）。她的车最多可以装下s升的汽油。在出发的时候，车的邮箱是满的，并且她在路上不想加油，即从城市u到城市v的过程中，她都不加油。
　　在路上，每经过一个城市，她要交一定的费用。如果她某次交的费用比较多，她的心情就会变得很糟。所以她想知道，在她能到达目的地的前提下，她交的费用中最多的一次最少是多少。这个问题对于她来说太难了，于是她找到了聪明的你，你能帮她吗？

Input

第一行5个正整数n,m,u,v,s
接下来有n行，每行1个正整数fi表示经过城市i，需要交费fi元。
再接下来有m行，每行3个正整数ai，bi，ci（1<=ai,bi<=n），表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi到城市ai，需要ci升汽油

Output

仅一个整数，表示小红交费最多的一次的最小值。
如果她无法到达城市v，输出-1。

Sample Input

Sample Output

输出样例1：
8


输出样例2：
-1

Hint

数据规模：
对于60%的数据，满足n≤200，m≤10000，s≤200
对于100%的数据，满足n≤10000，m≤50000，s≤1 000 000 000
对于100%的数据，满足ci≤1 000 000 000，fi≤1 000 000 000
可能有两条边连接着相同的城市

考虑二分答案则对于每次二分的值 S

将图中端点的收费大于S 的边删去

如果以油量为权跑完最短路 d[v]的值大于总油量则这次二分的值不是答案

以此扩展

因为数据过大且SPFA容易被卡边权无负我们选择Dijkstra算法来检查

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<map>
#define LL long long
#define f(a,b,c) for(long long i = (a); i <= (b); i += (c))
using namespace std;
long long n,m,u,v,s;
long long f[10000000],head[1000000];
long long a,b,t;
long long d[10000000],maxx;
map<pair<long long,long long >,bool>QWQ;
struct Edge{
    long long next,final,value;
}e[10000000];
struct node{
    long long to,value;
    bool operator <(const node &QWQ) const
   {
        return value > QWQ.value;
   }
};
inline void dis(long long ans)
{
    memset(d,0x3f,sizeof(d));
    d[u] = 0;
    priority_queue<node> QAQ;
    QAQ.push((node){u,0});
    while(!QAQ.empty())
    {
        long long u_ = QAQ.top().to;
        long long v_ = QAQ.top().value;
        QAQ.pop();
        if(f[u_] > ans) continue;
        if(v_ != d[u_]) continue;
        for(long long i = head[u_] ; i; i = e[i].next )
        {
            long long place = e[i].final;
            long long w = e[i].value;
            if(d[u_] + w < d[place])
            {
                d[place] = d[u_] + w ;
                QAQ.push((node){place,d[place]});
            }
        }
    }
}
void add_edge(long long begin,long long to,long long c)
{
    e[++e[0].value].final = to;
    e[e[0].value].value = c;
    e[e[0].value].next = head[begin];
    head[begin] = e[0].value;
}
int main()
{    
    scanf("%lld%lld%lld%lld%lld",&n,&m,&u,&v,&s);
    f(1,n,1) 
    {
        scanf("%lld",&f[i]);
        maxx = max(f[i],maxx);
    }
    f(1,m,1) 
    {
        scanf("%lld%lld%lld",&a,&b,&t);
        if(!QWQ[make_pair(a,b)])
        {
        add_edge(a,b,t);
        add_edge(b,a,t);
        QWQ[make_pair(a,b)] = QWQ[make_pair(b,a)] = 1;
        }
    }

    long long l = max(f[u],f[v]),r = maxx+2;
    dis(maxx);
    while(l <= r)
    {
        long long mid = (l + r )/2;
        dis(mid);
        if(d[v] > s)
        l = mid + 1;
        else
        r = mid ;       
    }
    if(d[v] > s)
    {
        cout<< -1;
        return 0;
    }
    return 0;
}

View Code

【NOI导刊200908模拟试题02 题4】【二分+Dijkstra】 收费站

【NOI导刊200908模拟试题02 题4】【二分+Dijkstra】收费站