中山網(wǎng)站建設前端開發(fā)
題目描述
松鼠寶寶由于貪玩去了一個具有n個點和m條邊的無向圖中，現(xiàn)在松鼠寶寶僅有h點體力，所有的邊經(jīng)過一次后會消耗部分體力，同時松鼠爸爸為了懲罰貪玩的松鼠寶寶，每到一個點會扣除部分松果（起點的松果也會扣除）?，F(xiàn)松鼠寶寶向你求助，詢問在能到達家的情況下
??????? 盡可能讓路徑上扣除松果的數(shù)量最大的那個點扣除的數(shù)量盡可能小。
輸入描述:
第一行讀入五個數(shù)n，m，st，ed， h（分別無向圖的點數(shù)，邊數(shù)，起點位置，家的位置，開始時候的體力）
接下來一行讀入n個數(shù)ai（每個點所扣除的松果數(shù)量）
接下來m行讀入x，y，z（分別代表無向邊的兩點和路上所消耗的體力）
1<=n <=1e4?
1<=m<= 2e4
1<=ai,z, h <= 1e7??
1 <= x,y <= n
輸出描述:
輸出一行代表最大扣除數(shù)量的最小值，若無法到達，則輸出-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;
}