再試合模擬試験問題-料金所Dijkstraディジェストラ+二分解答法重慶一中高2018級競技クラス第9回試験2016.9.10 Problem 4

【問題の説明】ある遠い国には、n都市がある.番号は1,2,3,...,nです.
この国の政府はm本の双方向の道路を建設した.道路ごとに2つの都市がつながっている.ある道路に沿って、ある都市から別の都市まで車を運転するには、一定のガソリンが必要です.
車で1つの都市を通るたびに、一定の費用(起点と終点都市を含む)が徴収されます.すべての料金所は都市の中にあり、都市間の道路には料金所がありません.
紅ちゃんは今、都市uから都市v(1<=u,v<=n)まで車で行きます.彼女の車はせいぜいsリットルのガソリンを入れることができる.出発する時、車のガソリンタンクはいっぱいで、彼女は道で給油したくない.
道では、都市を通るたびに、彼女は一定の費用を払わなければならない.もし彼女が一度に払う費用が多ければ、彼女の気持ちは悪くなります.だから彼女は目的地に着くことができる前提の下で、彼女が払った費用の中で一番多いのは最低いくらなのか知りたいと思っています.この問題は彼女にとって難しすぎて、そこで彼女は賢いあなたを見つけて、あなたは彼女を助けることができますか?
【入力フォーマット】第1行5個の正の整数、n,m,u,v,s.それぞれn都市,m道路があり,都市uから都市vまで,車のガソリンタンクの容量はsリットルであることを示した.次はn行で、行ごとに正の整数、fiが1つあります.都市iを通るにはfi元を払う必要があることを示しています.次にm行があり、行ごとに3つの正の整数、ai、bi、ci(1<=ai、bi<=n)があります.都市aiと都市biの間に道路があることを示し、都市aiから都市bi、または都市biから都市aiまで、ciリットルのガソリンが必要です.
【出力フォーマット】わずか1つの整数で、小紅が最も多くの費用を支払う最小値を表し、もし彼女が都市vに到着できない場合、出力-1を表す.
【入力サンプル】【サンプル1】

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

【様式2】

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

【出力サンプル】【サンプル1】

8

【様式2】

-1

【データ範囲】60%のデータに対して、n<=200、m<=10000、s<=200が100%のデータに対して、n<=10000、m<=50000、s<=1000,000が100%のデータに対して、ci<=1,000,000,fi<=1,000,000,000を満たし、2つの辺が同じ都市を結んでいる可能性がある.
考え方:長い間図論に関する問題をしていなかったので、もう忘れてしまった.最初に重み付きグラフの最短パス用SPFAアルゴリズムを考えたが,このアルゴリズムは時間的に複雑で,この問題のすべてのデータ点を通過できないためDijkstraディジェストラアルゴリズムを用いた.最大値は最小であり,一般的には二分解答法を用いるので,当てた答えをDijkstraと組み合わせて検証(すなわちdist[v]<=s)すればよい.

/*
    Name: toll.cpp
    Copyright: Twitter & Instagram @stevebieberjr
    Author: @stevebieberjr
    Date: 10/09/16 17:28
*/
#include
#include
#include
#include
#include
#define inf 0X3F3F3F3F
using namespace std;

int n,m,u,v,s,f[10005],dist[10005];
vector<int>g[10005],w[10005];

struct data
{
    int d,id;
    friend bool operator < (data a,data b)
    {
        return a.d>b.d;
    }
};

void Dij(int s,int *d,int limit)
{
    priority_queuepq;
    for(int i=1;i<=n;i++) d[i]=inf;
    pq.push((data){0,s});
    d[s]=0;

    while(!pq.empty())
    {
        data t=pq.top(); pq.pop();
        int i=t.id;
        if(f[i]>limit) continue;
        if(t.d>d[i]) continue;
        d[i]=t.d;

        for(int k=0;kint j=g[i][k],c=w[i][k];
            if(f[j]>limit) continue;
            if(d[i]+cint main()
{
    freopen("toll.in","r",stdin);
    freopen("toll.out","w",stdout);
    scanf("%d%d%d%d%d",&n,&m,&u,&v,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
    }

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        g[x].push_back(y);
        g[y].push_back(x);
        w[x].push_back(z);
        w[y].push_back(z);
    }

    int A=0,B=1000000000,ans;
    while(A<=B)
    {
        int mid=(A+B)/2;
        Dij(u,dist,mid);
        if(dist[v]<=s)
        {
            B=mid-1;
            ans=mid;
        }
        else
        {
            A=mid+1;
        }
    }
    if(B==1000000000)
    {
        printf("-1
");
    }
    else printf("%d
",ans);
    return 0;
}