一般网站栏目结构,网站怎么做才会有收录,网站建设方案书怎么写样版,wordpress取消邮件验证码题目描述 松鼠宝宝由于贪玩去了一个具有n个点和m条边的无向图中#xff0c;现在松鼠宝宝仅有h点体力#xff0c;所有的边经过一次后会消耗部分体力#xff0c;同时松鼠爸爸为了惩罚贪玩的松鼠宝宝#xff0c;每到一个点会扣除部分松果#xff08;起点的松果也会扣除#…
题目描述 松鼠宝宝由于贪玩去了一个具有n个点和m条边的无向图中现在松鼠宝宝仅有h点体力所有的边经过一次后会消耗部分体力同时松鼠爸爸为了惩罚贪玩的松鼠宝宝每到一个点会扣除部分松果起点的松果也会扣除。现松鼠宝宝向你求助询问在能到达家的情况下 尽可能让路径上扣除松果的数量最大的那个点扣除的数量尽可能小。 输入描述: 第一行读入五个数nmsted h分别无向图的点数边数起点位置家的位置开始时候的体力 接下来一行读入n个数ai每个点所扣除的松果数量 接下来m行读入xyz分别代表无向边的两点和路上所消耗的体力 1n 1e4 1m 2e4 1ai,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来写最短路 #includebits/stdc.h
using namespace std;
typedef long long ll;
typedef pairint,int PII;
const int M4e410;
const int N1e410;
const int INF0x3f3f3f3f;
int minn0x3f3f3f3f;
int maxn0xc0c0c0c0;
int dx[4]{0,0,1,-1};
int dy[4]{1,-1,0,0};
bool st[N];
ll val[N];
ll dist[N];
vectorPII v[N];
ll n,m,s,e,k,h,mx;
bool check(ll x)
{queuell q;q.push(s);for(int i1;in;i) dist[i]INF,st[i]false;dist[s]0;while(q.size()){ll uq.front();q.pop();st[u]false;for(int i0;iv[u].size();i){ll jv[u][i].first;ll wv[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()
{cinnmseh;for(int i1;in;i){cinval[i];mxmax(mx,val[i]);}while(m--){ll a,b,c;cinabc;v[a].push_back({b,c});v[b].push_back({a,c});}ll l0,rmx;ll mid;while(lr){midlr1;if(check(mid))rmid;else lmid1;}if(check(l))coutlendl;elsecout-1endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t1;
// cint;while(t--){ solve();}return 0;
}
