[洛谷 2939,4568][USACO09FEB/JLOI2011]飞行路线

双倍经验警告

题目链接

https://www.luogu.org/problem/P2939

https://www.luogu.org/problem/P4568

题解

分层图最短路板子题。

我们将状态增加一维，用 \(dist_{i,j}\) 表示在 \(i\) 号点，使用 \(j\) 次升级次数后的最短路。

每次转移时有两种决策：

1. 次数没用完时，可以选择用掉一次免费次数。
2. 不用免费次数。

剩下的就和普通最短路一样了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,next;
}e[100005];
struct node
{
 int p,used,dist;
 bool operator<(const node&a)const
 {
  return dist>a.dist;
 }
};
priority_queue<node> q;
int head[10005],dist[10005][25],vis[10005][25],n,m,s,t,k,cnt;
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void spfa()
{
 memset(dist,INF,sizeof(dist));
 dist[s][0]=0;
 q.push({s,0,0});
 while(!q.empty())
 {
  int u=q.top().p,used=q.top().used;
  q.pop();
  vis[u][used]=false;
  for(int i=head[u];i;i=e[i].next)
  {
   int v=e[i].v;
   if(used<=k&&dist[v][used+1]>dist[u][used])
   {
    dist[v][used+1]=dist[u][used];
    if(!vis[v][used+1])
    {
     q.push({v,used+1,dist[v][used+1]});
     vis[v][used+1]=true;
    }
   }
   if(dist[v][used]>dist[u][used]+e[i].w)
   {
    dist[v][used]=dist[u][used]+e[i].w;
    if(!vis[v][used])
    {
     q.push({v,used,dist[v][used]});
     vis[v][used]=true;
    }
   }
  }
 }
}
int main()
{
 scanf("%d%d%d",&n,&m,&k);
 scanf("%d%d",&s,&t);
 for(int i=1;i<=m;i++)
 {
  int u,v,w;
  scanf("%d%d%d",&u,&v,&w);
  addedge(u,v,w);
  addedge(v,u,w);
 }
 spfa();
 int ans=INF;
 for(int i=0;i<=k;i++)
  ans=min(ans,dist[t][i]);
 printf("%d\n",ans);
 return 0;
}