牛客 松鼠回家（二分答案+最短路）

题目描述

松鼠宝宝由于贪玩去了一个具有n个点和m条边的无向图中，现在松鼠宝宝仅有h点体力，所有的边经过一次后会消耗部分体力，同时松鼠爸爸为了惩罚贪玩的松鼠宝宝，每到一个点会扣除部分松果（起点的松果也会扣除）。现松鼠宝宝向你求助，询问在能到达家的情况下

        尽可能让路径上扣除松果的数量最大的那个点扣除的数量尽可能小。

输入描述:

第一行读入五个数n，m，st，ed， h（分别无向图的点数，边数，起点位置，家的位置，开始时候的体力）

接下来一行读入n个数ai（每个点所扣除的松果数量）

接下来m行读入x，y，z（分别代表无向边的两点和路上所消耗的体力）

1<=n <=1e4 

1<=m<= 2e4

1<=ai,z, h <= 1e7  

1 <= x,y <= n

输出描述:

输出一行代表最大扣除数量的最小值，若无法到达，则输出-1

示例1

输入

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

输出

10

学习学长用bfs来写最短路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int M=4e4+10;
const int N=1e4+10;
const int INF=0x3f3f3f3f;
int minn=0x3f3f3f3f;
int maxn=0xc0c0c0c0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool st[N];
ll val[N];
ll dist[N];
vector<PII> v[N];
ll n,m,s,e,k,h,mx;
bool check(ll x)
{queue<ll> q;q.push(s);for(int i=1;i<=n;i++) dist[i]=INF,st[i]=false;dist[s]=0;while(q.size()){ll u=q.front();q.pop();st[u]=false;for(int i=0;i<v[u].size();i++){ll j=v[u][i].first;ll w=v[u][i].second;if(val[j]>x) continue;if(dist[j]>dist[u]+w){dist[j]=dist[u]+w;if(!st[j]){st[j]=true;q.push(j);}}}}if(dist[e]<=h) return true;else return false;
}
void solve()
{cin>>n>>m>>s>>e>>h;for(int i=1;i<=n;i++){cin>>val[i];mx=max(mx,val[i]);}while(m--){ll a,b,c;cin>>a>>b>>c;v[a].push_back({b,c});v[b].push_back({a,c});}ll l=0,r=mx;ll mid;while(l<r){mid=l+r>>1;if(check(mid))r=mid;else l=mid+1;}if(check(l))cout<<l<<endl;elsecout<<-1<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t=1;
//	cin>>t;while(t--){	solve();}return 0;
}