@[Humour_Fz](/user/1056908) 看到没，压行是不会有人帮你调的
by DFs_YYDS @ 2024-03-07 18:57:32
@[Humour_Fz](/user/1056908)
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Gra{
ll v,w;
Gra(ll v,ll w):v(v),w(w){};
};
vector<Gra> adj[10010];
struct D{
ll end,len;
D(ll end,ll len):end(end),len(len){};
bool operator<(const D &x)const{
return len>x.len;
}
};
priority_queue<D> q;
ll v[10010],dis[10010],n,m,b,u,vv,w,c[10010],l,r,ans=-1;
ll check(ll k){
memset(v,0,sizeof(v));//清零
memset(dis,0x3f,sizeof(dis));//清零
while(!q.empty()) q.pop();//清空
q.push({1,0});
dis[1]=0;
while(!q.empty()){
ll x=q.top().end,y=q.top().len;
q.pop();
if(v[x]==1) continue;//如果是秀的话，就跳过
v[x]=1;//标记为秀
for(int i=0;i<adj[x].size();i++){//儿子们
ll nx=adj[x][i].v,ny=adj[x][i].w;
if(v[nx]==1) continue;
if(v[nx]==0&&c[nx]<=k&&dis[x]+ny<=b&&dis[nx]>=dis[x]+ny){
//如果不是秀并且猜测的最大花费>=这个点的花费并且比血量<=原始血量并且可以更新更好的点
dis[nx]=dis[x]+ny;//更新
q.push({nx,dis[nx]});//入队
}
}
}
if(dis[n]>=0x3f3f3f3f) return 0;//如果不存在，那么返回0
return 1;//存在，返回1
}
int main(){
cin>>n>>m>>b;
for(int i=1;i<=n;i++){
cin>>c[i];
r=max(r,c[i]);
}
l=c[1];
for(int i=1;i<=m;i++){
cin>>u>>vv>>w;
adj[u].push_back({vv,w});//无向图
adj[vv].push_back({u,w});
}
while(l<=r){//二分猜答案
ll mid=(l+r)/2;
if(check(mid)==1){//如果可以，那么记录，继续看看有没有更好的
ans=mid;//记录答案
r=mid-1;//继续看看有没有更好的
}else l=mid+1;//不可以，继续猜
}
if(ans==-1) cout<<"AFK";//如果到不了
else cout<<ans;//到得了
return 0;
}
```
by lutaoquan2012 @ 2024-03-07 20:27:47
@[lutaoquan2012](/user/952033) 请问我哪里有问题？
by Humour_Fz @ 2024-03-07 20:40:38
@[Humour_Fz](/user/1056908) 看起来没有什么问题，但是实则我也没对，一直是80分，但是数据11过了
```cpp
//
// Created by 55062 on 2024/3/7.
//
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 100, M = 5e4 + 100, inf = 0x3f3f3f3f;
struct edge {
int nxt, to, dis;
} e[M << 1];
struct node {
int x, dis;
bool operator<(const node &x) const {
return x.dis < dis;
}
};
int n, m, b, s, u, v, w, l, r, ans, cnt, f[N], head[N], vis[N], dis[N];
priority_queue<node> q;
void add(int a, int b, int c) {
++cnt;
e[cnt].dis = c;
e[cnt].to = b;
e[cnt].nxt = head[a];
head[a] = cnt;
}
int dij(int mx) {
memset(vis, 0, sizeof vis);
while(!q.empty()) q.pop();
for (int i = 1; i <= n; i++) dis[i] = inf;
dis[s] = 0;
q.push({s, 0});
while (!q.empty()) {
node fr = q.top();
q.pop();
if (vis[fr.x]) continue;
vis[fr.x] = 1;
for (int i = head[fr.x]; i; i = e[i].nxt) {
int t = e[i].to;
if(vis[t]==1) continue;
if (f[t] <= mx && dis[t] > dis[fr.x] + e[i].dis&&vis[t]==0&&dis[t]>=dis[fr.x]+e[i].dis) {
dis[t] = dis[fr.x] + e[i].dis;
if (!vis[t]) q.push({t, dis[t]});
}
}
}if(dis[n]>=0x3f3f3f3f) return 0;
return 1;
}
signed main() {
cin >> n >> m >> b;
s = 1;
for (int i = 1; i <= n; i++) {
cin >> f[i];
r = max(r, f[i]);
}
l = f[1];
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
while (l <= r) {
int mid = l + r >> 1;
if (dij(mid)){
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
return ans ? cout << ans : cout << "AFK", 0;
}
```
by lutaoquan2012 @ 2024-03-07 20:56:29
@[Humour_Fz](/user/1056908) 你能确定你的链式前向星是对的么？我不会，所以没查
by lutaoquan2012 @ 2024-03-07 20:58:43
@[lutaoquan2012](/user/952033) 从板子里复制的/cf
by Humour_Fz @ 2024-03-07 21:01:54
@[Humour_Fz](/user/1056908) 因该可以
by lutaoquan2012 @ 2024-03-07 21:02:12