为什么全是AFK啊QAQ

Ch3lly @ 2017-11-08 15:15:07

#include<bits/stdc++.h>
#define maxn 100001
typedef long long LL;
using namespace std;
LL cost[maxn];
LL n,m,b,ai,bi,ci;
inline void read(LL &a)
{
    int ch=0;bool f=0;a=0;
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){a=(a<<3)+(a<<1)+ch-'0';ch=getchar();}
    if(f)a=-a;
}
//------------------------spfa---------------------------
LL head[maxn],dis[maxn],vis[maxn];
struct eg{LL to,nxt,val;}e[maxn];
LL cnt=0;
inline void addedge(LL fr,LL to,LL val)
{
    e[++cnt].to=to;
    e[cnt].val=val;
    e[cnt].nxt=head[fr];
    head[fr]=cnt;
}
inline void spfa(LL mid)
{
    memset(vis,false,sizeof vis);
    memset(dis,0x7f,sizeof dis);
    queue<LL>q;
    dis[1]=0;vis[1]=1;q.push(1);
    while(!q.empty())
    {
        LL u=q.front();q.pop();vis[u]=0;
        for(LL i=head[u];i;i=e[i].nxt)
        {
            LL v=e[i].to;LL w=e[i].val;
            if(cost[v]<=mid&&dis[v]<dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    vis[v]=1;q.push(v);
                }
            }
        }
    }    
}
inline void insert(LL aa,LL bb,LL cc)
{
    addedge(aa,bb,cc);
    addedge(bb,aa,cc);
}
//-----------------------二分------------------------ 
inline bool chk(LL mid)
{
    if(dis[n]>=b) return false;
    else return true;
}
int main()
{
    memset(head,-1,sizeof head);
    memset(dis,0x7f,sizeof dis);
    read(n);read(m);read(b);
    LL l=20000000006,r=0;
    for(int i=1;i<=n;i++)
    {
        read(cost[i]);
        r=max(r,cost[i]);
        l=min(l,cost[i]);
    }
    for(int i=1;i<=m;i++)
    {
        read(ai);read(bi);read(ci);
        insert(ai,bi,ci);
    }
    spfa(r); if(dis[n]>=b) return cout<<"AFK",0;
    while(l<=r)
    {
        LL mid=(l+r)>>1;
        spfa(mid);
        if(chk(mid)) r=mid-1;
        else l=mid+1; 
    }
    cout<<l;
    return 0;
}

by Ch3lly @ 2017-11-08 15:47:48

求大佬来啊qwq

by Hammer_cwz_77 @ 2017-11-08 19:21:20

我也是QAQ

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <climits>
#include   <cstdio>
#include   <string>
#include    <cmath>
#include    <stack>
#include    <queue>
using namespace std;
const int gg=100000;
int n,m,b;
struct node{
    int next;
    int to;
    int w;
}a[gg];
int dis[gg];
int head[gg];
bool vis[gg];
int x[gg];
int cnt;
int p[gg];
int l,r;
inline void add(int i,int j,int w)
{
    a[cnt].w=w;
    a[++cnt].to=i;
    a[cnt].next=head[i];
    head[i]=cnt;
}
inline bool spfa(int s)
{
    queue<int> q;
    memset(vis,false,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
    q.push(s);
    vis[s]=true;
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u];i!=-1;i=a[i].next)
        {
            int v=a[i].to;
            if(p[v]<=s&&dis[v]>dis[u]+a[i].w)
            {
                dis[v]=dis[u]+a[i].w;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
}
inline int ef(int l,int r)
{
    l=1;
    r=n;
    int mid;
    int ans=0;
    while(l<=n)
    {
        mid=l+(r-l)/2;
        if(spfa(mid))
        {
            ans=x[mid];
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    return ans;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
    }
    sort(x+1,x+n+1);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    if(dis[n]<=0)
    {
        cout<<"AFK"<<endl;
        return 0;
    }
    cout<<ef(l,r)<<endl;
    return 0;
}

by XiaoX @ 2018-06-04 15:59:39

sort？