ub?
查看原帖
ub?
682390
quliannanyishou楼主2022/10/8 21:44

为什么cnt++要写成cnt+=1?

#include<bits/stdc++.h>
using namespace std;
long long n,m,h,last[10001],cnt=1,s,cost[10001],l,r=-1,mid,max1;
bool vis[10001];
struct hh
{
    long long next;
    long long to;
    long long val;
}a[100001];
struct node
{
    long long dis;
    long long num;
    bool operator<(const node&x) const
    {
        return dis>x.dis;
    }
}b[10001];
priority_queue<node,vector<node> > q;
bool dij()
{
    if(mid<cost[1])
    {
        return 1;
    }
    q=priority_queue<node,vector<node> >();
    for(int i=1;i<=n;++i)
    {
        b[i].dis=9223372036854775807;
        b[i].num=i;
        vis[i]=0;
    }
    b[1].dis=0;
    q.push(b[1]);
    while(!q.empty())
    {
        int now=q.top().num;
        q.pop();
        if(vis[now])
        {
            continue;
        }
        vis[now]=1;
        for(int i=last[now];i;i=a[i].next)
        {
            if(!vis[a[i].to]&&b[a[i].to].dis>b[now].dis+a[i].val&&mid>=cost[a[i].to])
            {
                b[a[i].to].dis=b[now].dis+a[i].val;
                q.push(b[a[i].to]);
            }
        }
    }
    if(b[n].dis>h)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    //freopen("P1462_5.in","r",stdin);
    cin>>n>>m>>h;
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&cost[i]);
        r=max(r,cost[i]);
    }
    l=max(cost[1],cost[n]);
    max1=r;
    for(int i=1;i<=m;++i)
    {
        scanf("%lld%lld%lld",&s,&a[cnt].to,&a[cnt].val);
        a[cnt].next=last[s];
        last[s]=cnt++;//这里
        a[cnt].val=a[cnt-1].val;
        a[cnt].to=s;
        a[cnt].next=last[a[cnt-1].to];
        last[a[cnt-1].to]=cnt++;//和这里
    }
    while(l<r)
    {
        mid=(l+r)>>1;
        if(dij())
        {
            l=mid+1;
        }
        else
        {
            r=mid;
        }
    }
    mid=max1;
    if(dij())
    {
        cout<<"AFK";
    }
    else
    {
        cout<<l;
    }
}
2022/10/8 21:44
加载中...