luogu P4568 [JLOI2011]飞行路线

传送门

看到免费次数\(k\)最多只有10,可以考虑构建\(k+1\)层的分层图,即每一层正常连边,上下两层对应点连边权为0的单向边,最后对所有层里面的\(di_t\)取\(\max\)救星了

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define db double

#define eps (1e-5)

using namespace std;

const int N=10000+10,M=50000+10;

il LL rd()

{

    re LL x=0,w=1;re char ch;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int to[(M*22)<<1],nt[(M*22)<<1],w[(M*22)<<1],hd[N*11],tot=1;

il void add(int x,int y,int z){++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;}

struct node

{

  int x,d;

  bool operator < (const node &bb) const {return d>bb.d;}

};

int n,m,kk,ss,tt,ed,di[N*11];

int main()

{

  n=rd(),m=rd(),kk=rd(),ss=rd(),tt=rd();

  for(int i=1;i<=m;i++)

    {

      int x=rd(),y=rd(),z=rd();

      for(int j=0;j<=kk;j++) add(x+j*n,y+j*n,z),add(y+j*n,x+j*n,z);

      for(int j=0;j<kk;j++) add(x+j*n,y+(j+1)*n,0),add(y+j*n,x+(j+1)*n,0);

    }

  ed=n*(kk+1);

  for(int j=0;j<=kk;j++) add(tt+j*n,ed,0);

  memset(di,63,sizeof(di));

  di[ss]=0;

  priority_queue<node> q;

  q.push((node){ss,0});

  while(!q.empty())

    {

      int x=q.top().x,d=q.top().d;

      q.pop();

      if(d>di[x]) continue;

      for(int i=hd[x];i;i=nt[i])

        {

          int y=to[i];

          if(di[y]>di[x]+w[i])

            {

              di[y]=di[x]+w[i];

              q.push((node){y,di[y]});

            }

        }

    }

  printf("%d\n",di[ed]);

  return 0;

}