[JLOI2011]飞行路线题解

文章目录

• [JLOI2011]飞行路线题解
• • 题目描述
  • 分析
  • 代码
  • • 注意：

题目描述

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 n n n个城市设有业务，设这些城市分别标记为 0 0 0到 n − 1 n-1 n−1，一共有 m m m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

分析

如果这个航空公司不这么DL(不要问我这是啥)，就直接跑一遍dijkstra求出最短路就行了。
但Alice和Bob选了这家DL航空公司，那怎么办呢？
我们能想到的就是在状态里加上优惠了几次。
就像这样：

struct node
{
	int x,w,k;
	bool operator<(const node&a)const
    {
    	if(a.w==w)return k<a.k;//k越小就越优
        return w>a.w;
    } 
};

int dis[10010][20],vis[10010][20];

松弛时

if(d[y.x][x.k]>d[x.x][x.k]+y.w&&!b[y.x][x.k])
{
	d[y.x][x.k]=d[x.x][x.k]+y.w;
	q.push(node{y.x,d[y.x][x.k],x.k});
}
if(x.k+1<=k&&d[y.x][x.k+1]>d[x.x][x.k]&&!b[y.x][x.k+1])
{
	d[y.x][x.k+1]=d[x.x][x.k];
	q.push(node{y.x,d[y.x][x.k+1],x.k+1});
}

代码

注意：

1.k是从零开始 （我调了20min）
2.城市编号也是从零开始的

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t,d[10010][20],b[10010][20];
struct node
{
	int x,w,k;
	bool operator<(const node&a)const
    {
    	if(a.w==w)return k<a.k;
        return w>a.w;
    } 
};
vector<node> v[10010];
void dijkstra(int s)
{
	priority_queue<node> q;
	memset(d,0x3f,sizeof(d));
	for(int i=0;i<=k;i++)d[s][i]=0;
	q.push(node{s,0,0});
	while(!q.empty())
	{
		node x=q.top();
		q.pop();
		if(b[x.x][x.k])continue;
		b[x.x][x.k]=1;
		for(int i=0;i<v[x.x].size();i++)
		{
			node y=v[x.x][i];
			if(d[y.x][x.k]>d[x.x][x.k]+y.w&&!b[y.x][x.k])
			{
				d[y.x][x.k]=d[x.x][x.k]+y.w;
				q.push(node{y.x,d[y.x][x.k],x.k});
			}
			if(x.k+1<=k&&d[y.x][x.k+1]>d[x.x][x.k]&&!b[y.x][x.k+1])
			{
				d[y.x][x.k+1]=d[x.x][x.k];
				q.push(node{y.x,d[y.x][x.k+1],x.k+1});
			}
		}
	}
}
int main()
{
	cin>>n>>m>>k>>s>>t;
	s++;
	t++;
	for(int i=1,x,y,z;i<=m;i++)
	{
		cin>>x>>y>>z;
		x++;
		y++;
		v[x].push_back(node{y,z,0});
		v[y].push_back(node{x,z,0});
	}
	dijkstra(s);
	int minn=2e9+10;
	for(int i=0;i<=k;i++)minn=min(d[t][i],minn);
	cout<<minn;

	return 0;
}