游客 注册 | 登录
中文 | En

3853 - 飞行路线

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

题目输入

数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。

第二行有两个整数，s,t，分别表示他们出行的起点城市编号和终点城市编号。(0<=s,t<n)

接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。(0<=a,b<n,a与b不相等，0<=c<=1000)

题目输出

只有一行，包含一个整数，为最少花费。

输入/输出样例

输入格式

5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

输出格式

8
HINT
对于30%的数据,2<=n<=50,1<=m<=300,k=0;
对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;

对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.

C++解答

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,k,tot,x,y,z,first[10005],dis[10005][12],v[10005][12],qi,zh;
struct bian
{
	int from,to,next,fare;
}s[100005];
void add(int x,int y,int z)
{
	s[++tot].from=x;
	s[tot].to=y;
	s[tot].fare=z;
	s[tot].next=first[x];
	first[x]=tot;
}
struct data
{
	int q,t,jvli;
	friend bool operator < (data a,data b)
	{
		return a.jvli>b.jvli;
	}
}cc,cd;
priority_queue<data>q;
void spfa(int x)
{
	memset(dis,50,sizeof(dis));
	memset(v,0,sizeof(v));
	cc.q=x;
	cc.jvli=0;
	cc.t=0;
	v[x][0]=1;
	q.push(cc);
	dis[x][0]=0;
	while(!q.empty())
	{
		cd=q.top();
		v[cd.q][cd.t]=0;
		q.pop();
		for(int i=first[cd.q];i!=-1;i=s[i].next)
		{
			int j=s[i].to;
			if(cd.t+1<=k)
			{
				if(dis[j][cd.t+1]>dis[cd.q][cd.t])
				{
					dis[j][cd.t+1]=dis[cd.q][cd.t];
					if(!v[j][cd.t+1])
					{
						v[j][cd.t+1]=1;
						cc.q=j;
						cc.jvli=dis[j][cd.t+1];
						cc.t=cd.t+1;
						q.push(cc);
					}
				}
			}
			if(dis[j][cd.t]>dis[cd.q][cd.t]+s[i].fare)
			{
				dis[j][cd.t]=dis[cd.q][cd.t]+s[i].fare;
				if(!v[j][cd.t])
				{
					v[j][cd.t]=1;
					cc.q=j;
					cc.jvli=dis[j][cd.t];
					cc.t=cd.t;
					q.push(cc);
				}
			}
		}
	}
}
int minc(int a,int b){return a<b?a:b;}
int main()
{
	//freopen("meg.in","r",stdin);
	//freopen("meg.out","w",stdout);
	memset(first,-1,sizeof(first));
	scanf("%d%d%d%d%d",&n,&m,&k,&qi,&zh);
	qi++,zh++;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		x++,y++;
		add(x,y,z);
		add(y,x,z);
	}
	spfa(qi);
	int ans=0x7fffffff;
	for(int i=0;i<=k;++i)
		ans=minc(dis[zh][i],ans);
	printf("%d",ans);
	//while(1);
}/*
5 6 1 0 4 0 1 5 1 2 5 2 3 5 3 4 5 2 3 3 0 2 100
*/
请先登陆