设计本官方网站广告2023推广平台
题目描述
松鼠宝宝由于贪玩去了一个具有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;
}