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:58:12
@ud2_ c++98也是吗,我选的c++98
by Hisaishi_Kanade @ 2022-10-08 21:59:44
这玩意好像是到C++17(?)之后才有明确规定
by quliannanyishou @ 2022-10-08 22:04:04
@bye_wjx 可我交的是c++98,so,洛谷的锅?
by 初雪_matt @ 2022-10-08 22:07:25
@quliannanyishou c++98<c++17这没问题啊
by quliannanyishou @ 2022-10-08 22:13:47
@初雪_matt 啊这,我一直以为c++98>c++17
by ud2_ @ 2022-10-08 22:13:49
或者说,1998 < 2017(C++ 标准命名什么时候改用 4 位数年份
by quliannanyishou @ 2022-10-08 22:16:51
@ud2_ 我好像没有常识,这样的我初赛能过也是个奇迹
by Konjac_16 @ 2022-10-08 22:21:53
每日一笑