quliannanyishou @ 2022-10-08 21:44:22
为什么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;
}
}by quliannanyishou @ 2022-10-08 21:46:21
@quliannanyishou 因为这个我交了十几遍，艹
by itisover @ 2022-10-08 21:46:53
cnt++ => last[s]=cnt; cnt+=1;
++cnt => cnt+=1; last[s]=cnt;
by Eafoo @ 2022-10-08 21:47:25
@quliannanyishou https://blog.csdn.net/weixin_41758423/article/details/107412559
by Hisaishi_Kanade @ 2022-10-08 21:47:29
cnt++ 返回原来的 cnt，cnt+=1 返回原来 cnt+1 的值
by quliannanyishou @ 2022-10-08 21:47:44
@Eafoo 对啊，我cnt是从1开始的，应该没问题吧
by tin_ingot @ 2022-10-08 21:48:09
@quliannanyishou 对，正如他们所说的，因该改成++cnt合适些
by Eafoo @ 2022-10-08 21:49:53
@quliannanyishou 呃呃，自增放后面 bug 特别多，复杂点的建议在整个语句后面再写++
by quliannanyishou @ 2022-10-08 21:50:14
@quliannanyishou 我的意思是改成这样，是我表述不清
#include<bits/stdc++.h>
using namespace std;
long long n,m,h,last[10001],cnt=1,s,cost[10001],l,r=-9223372035477507,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(long long i=1;i<=n;++i)
{
b[i].dis=9223372035477507;
b[i].num=i;
vis[i]=0;
}
b[1].dis=0;
q.push(b[1]);
while(!q.empty()&&!vis[n])
{
long long now=q.top().num;
q.pop();
if(vis[now])
{
continue;
}
vis[now]=1;
for(long long i=last[now];i;i=a[i].next)
{
if(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(!vis[n]||b[n].dis>h)
{
return 1;
}
else
{
return 0;
}
}
int main()
{
cin>>n>>m>>h;
for(long long i=1;i<=n;++i)
{
scanf("%lld",&cost[i]);
r=max(r,cost[i]);
}
l=max(cost[1],cost[n]);
max1=r;
for(long long i=1;i<=m;++i)
{
scanf("%lld%lld%lld",&s,&a[cnt].to,&a[cnt].val);
a[cnt].next=last[s];
last[s]=cnt;
cnt+=1;
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;
cnt+=1;
}
while(l<r)
{
mid=(l+r)>>1;
if(dij())
{
l=mid+1;
}
else
{
r=mid;
}
}
mid=max1;
if(dij())
{
cout<<"AFK";
}
else
{
cout<<l;
}
}by quliannanyishou @ 2022-10-08 21:54:07
@Eafoo @bye_wjx @滑稽人 @S11EDG ++cnt还是有错，只能写cnt+=1，why？ https://www.luogu.com.cn/record/89191662
by ud2_ @ 2022-10-08 21:54:57
两种写法都是错的。C++14 没有规定等号前面的 cnt - 1 和等号后面的 cnt++ 应该先算哪个，这确实是 UB。