[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;
}
上一篇:洛谷 P1455 搭配购买


下一篇:Nginx 设置未绑定域名禁止访问