Humour_Fz @ 2024-03-07 16:58:10
rt,WA#7#8#11
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+100,M=5e4+100,inf=1e18;
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);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(f[t]<=mx&&dis[t]>dis[fr.x]+e[i].dis){
dis[t]=dis[fr.x]+e[i].dis;
if(!vis[t])q.push({t,dis[t]});
}
}
}return dis[n]<=mx;
}signed main(){
cin>>n>>m>>b,s=1;
for(int i=1;i<=n;i++)cin>>f[i],r=max(r,f[i]);l=max(f[1],f[n]);
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 DFs_YYDS @ 2024-03-07 18:57:32
@Humour_Fz 看到没，压行是不会有人帮你调的
by lutaoquan2012 @ 2024-03-07 20:27:47
@Humour_Fz
#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 Humour_Fz @ 2024-03-07 20:40:38
@lutaoquan2012 请问我哪里有问题？
by lutaoquan2012 @ 2024-03-07 20:56:29
@Humour_Fz 看起来没有什么问题，但是实则我也没对，一直是80分，但是数据11过了
//
// 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:58:43
@Humour_Fz 你能确定你的链式前向星是对的么？我不会，所以没查
by Humour_Fz @ 2024-03-07 21:01:54
@lutaoquan2012 从板子里复制的/cf
by lutaoquan2012 @ 2024-03-07 21:02:12
@Humour_Fz 因该可以