求救求救
by truekun @ 2024-01-29 16:59:41
求救
by truekun @ 2024-01-30 09:35:39
小改了几处：
+ 输入fi的时候一共n个点，循环从1到n而不是从1到m
+ dijkstra初始化dis的时候5e4不够大，可以改成0x3f3f3f3f
+ check最后返回的时候，dis[n]可以等于b（血量不为负就行）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int inf=5e4 + 5;
int f[inf];
int vis[inf];
priority_queue< pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct node{
int y,z;
};
int dis[inf];
int n,m,b;
vector <node> E[inf];
bool check(int mid){
if(f[1]>mid) return false;
for(int i=1;i<=n;i++){
dis[i]=0x3f3f3f3f;
vis[i]=0;
}
dis[1] = 0;
while(!q.empty()) q.pop();
//printf("ok\n");
q.push({0,1});
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u]){
continue;
}
//printf("u=%d dis=%d\n",u,dis[u]);
vis[u]=1;
for(auto ed:E[u]){
int v=ed.y,w=ed.z;
if(f[v] > mid) continue;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(make_pair(dis[v],v));
}
}
}
//printf("mid=%d %d %d\n",mid,dis[n],b);
if(dis[n]<=b){
return true;
}else{
return false;
}
}
int main(){
cin>>n>>m>>b;
for(int i=1;i<=n;i++){
cin>>f[i];
}
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
E[x].push_back((node){y,z});
E[y].push_back((node){x,z});
}
//printf("check=%d\n",check(100));
//printf("check=%d\n",check(100));
//return 0;
int l=max(f[1], f[n]),r=1e9, ans = 0x3f3f3f3f;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans = mid;
r=mid-1;
}else{
l=mid+1;
}
}
if(ans == 0x3f3f3f3f){
cout<<"AFK";
}else{
cout<<ans;
}
return 0;
}
```
by Doppler @ 2024-01-30 12:21:52
@[Doppler](/user/782049) 膜拜dalao
by truekun @ 2024-01-30 16:38:13
@[truekun](/user/742462) 已经AC（4年级小学生诚心感谢）
by truekun @ 2024-01-30 16:39:05