#13WA，球条，玄关

YONEX @ 2024-08-11 10:51:15

#include<bits/stdc++.h>
using namespace std;
struct node
{
int to;
int len;
int next;
}
e[100005];

int head[100005],num;
long long dis[100005];
int n,m,b;
long long f[100005];

void add(int from,int to,int dis)
{
    e[++num].to=to;
    e[num].len=dis;
    e[num].next=head[from];
    head[from]=num;
}

const int INF=1e9;
priority_queue < pair< long long , int > > q; 
bool vis[100005];

long long dijkstra(int mid)
{
    // if(f[1]>mid)return 1;
    for(int i=1;i<=n;i++)dis[i]=INF;
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int t=q.top().second;q.pop();
        if(vis[t])
        {
            continue;
        }
        vis[t]=1;
        for(int j=head[t] ; j ; j=e[j].next)
        {
            if(dis[e[j].to]>dis[t]+e[j].len and f[e[j].to]<=mid)
            {
                dis[e[j].to] = dis[t]+e[j].len;
                q.push(make_pair(-dis[e[j].to],e[j].to));
            }
        }
    }
    return dis[n];
}

bool check(int mid)
{
    if(dijkstra(mid)<=b)
    {
        return 1;
    }
    else return 0;
}

int ac(int l,int r)
{
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    return l;
}

int main()
{
    cin>>n>>m>>b;
    long long maxx=-1;
    for(int i=1;i<=n;i++)cin>>f[i],maxx=max(maxx,f[i]);
    for(int i=1;i<=m;i++)
    {
        int u,v,l;cin>>u>>v>>l;
        add(u,v,l);add(v,u,l);
    }
    if(!check(maxx))
    {
    cout<<"AFK";
    return 0;
    }
    cout<<ac(1,maxx);
    return 0;
}

by lianchanghua @ 2024-08-11 11:07:57

@YONEX

#include<bits/stdc++.h>
using namespace std;
struct node
{
int to;
int len;
int next;
}
e[100005];

int head[100005],num;
long long dis[100005];
int n,m,b;
long long f[100005];

void add(int from,int to,int dis)
{
    e[++num].to=to;
    e[num].len=dis;
    e[num].next=head[from];
    head[from]=num;
}

const int INF=1e9;
priority_queue < pair< long long , int > > q; 
bool vis[100005];

long long dijkstra(int mid)
{
    if(f[1]>mid)return b+1;
    for(int i=1;i<=n;i++)dis[i]=INF;
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int t=q.top().second;q.pop();
        if(vis[t])
        {
            continue;
        }
        vis[t]=1;
        for(int j=head[t] ; j ; j=e[j].next)
        {
            if(dis[e[j].to]>dis[t]+e[j].len and f[e[j].to]<=mid)
            {
                dis[e[j].to] = dis[t]+e[j].len;
                q.push(make_pair(-dis[e[j].to],e[j].to));
            }
        }
    }
    return dis[n];
}

bool check(int mid)
{
    if(dijkstra(mid)<=b)
    {
        return 1;
    }
    else return 0;
}

int ac(int l,int r)
{
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    return l;
}

int main()
{
    cin>>n>>m>>b;
    long long maxx=-1;
    for(int i=1;i<=n;i++)cin>>f[i],maxx=max(maxx,f[i]);
    for(int i=1;i<=m;i++)
    {
        int u,v,l;cin>>u>>v>>l;
        add(u,v,l);add(v,u,l);
    }
    if(!check(maxx))
    {
    cout<<"AFK";
    return 0;
    }
    cout<<ac(1,maxx);
    return 0;
}

by lianchanghua @ 2024-08-11 11:10:43

@YONEX 当 f_1 > mid 的说明没有解，这时候就要退出了，可以直接返回 b+1。（我看你原来不是考虑到了么)

by julihui325 @ 2024-08-11 11:20:56

@YONEX 楼上说的对

 #include<bits/stdc++.h>
using namespace std;
struct node {
    int to;
    int w;
    int next;
} e[100005];

int head[100005],num;
long long dis[100005];
int n,m,b;
long long f[100005];

void add(int from,int to,int dis) {
    e[++num].to=to;
    e[num].w=dis;
    e[num].next=head[from];
    head[from]=num;
}

const int INF=1e9;
priority_queue < pair< long long , int > > q;
bool vis[100005];

bool dijkstra(int mid) {
    if(f[1]>mid)return 0;
    for(int i=1; i<=n; i++)dis[i]=INF;
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()) {
        int t=q.top().second;
        q.pop();
        if(vis[t]) {
            continue;
        }
        vis[t]=1;
        for(int j=head[t] ; j ; j=e[j].next) {
            if(dis[e[j].to]>dis[t]+e[j].w && f[e[j].to]<=mid) {
                dis[e[j].to] = dis[t]+e[j].w;
                q.push(make_pair(-dis[e[j].to],e[j].to));
            }
        }
    }
    return (dis[n]<=b);
}

//bool check(int mid) {
//  if(dijkstra(mid)<=b) {
//      return 1;
//  } else return 0;
//}

int ac(int l,int r) {
    while(l<r) {
        int mid=(l+r)/2;
        if(dijkstra(mid)) {
            r=mid;
        } else {
            l=mid+1;
        }
    }
    return l;
}

int main() {
    cin>>n>>m>>b;
    long long maxx=-1;
    for(int i=1; i<=n; i++) {
        cin>>f[i];
        maxx=max(maxx,f[i]);
    }
    for(int i=1; i<=m; i++) {
        int u,v,l;
        cin>>u>>v>>l;
        add(u,v,l);
        add(v,u,l);
    }
    if(!dijkstra(maxx)) {
        cout<<"AFK";
        return 0;
    }
    cout<<ac(1,maxx);
    return 0;
}

by julihui325 @ 2024-08-11 11:21:52

@YONEX 跟楼上改的马蜂不太一样，思路一样

by YONEX @ 2024-08-11 14:51:49

@julihui325 okokO(∩_∩)O谢谢

by YONEX @ 2024-08-11 14:52:08

@lianchanghua hhh，谢谢