Description
Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务,设这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少?
Input
数据的第一行有三个整数,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)
Output
只有一行,包含一个整数,为最少花费。
Sample Input
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
Sample Output
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.
题解
带限制的最短路,13年noip前的清北学堂罗雨屏讲的图论中有提到过类似的。如果k在3以下,还可以拆点变成一个有层次的图做。而这题k稍微大了点,怕拆点后边太多会爆内存,所以就可以写成二维带限制的最短路。
Ps:裸跑spfa6000多ms,加了SLF优化后快了不止一点点,300多ms就过了。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define ll long long #define MAXN 10002 using namespace std; int n,m,K,S,T,zz,head[MAXN]; struct bian{int to,nx,v;} e[MAXN*10]; struct dui{int w,c;} q[MAXN*10]; int dis[MAXN][12],pd[MAXN][12],ans; void insert(int x,int y,int z) { zz++; e[zz].to=y; e[zz].v=z; e[zz].nx=head[x]; head[x]=zz; zz++; e[zz].to=x; e[zz].v=z; e[zz].nx=head[y]; head[y]=zz; } void init() { scanf("%d%d%d",&n,&m,&K); scanf("%d%d",&S,&T); int i,x,y,z; for(i=1;i<=m;i++) {scanf("%d%d%d",&x,&y,&z); insert(x,y,z); } } void spfa() { int t=0,w=1,i,x,ct,p; memset(dis,127,sizeof(dis)); q[0].w=S; q[0].c=0; dis[S][0]=0; pd[S][0]=1; while(t!=w) {x=q[t].w; ct=q[t].c; t=(t+1)%100000; for(i=head[x];i;i=e[i].nx) {p=e[i].to; if(dis[p][ct]>dis[x][ct]+e[i].v) {dis[p][ct]=dis[x][ct]+e[i].v; if(!pd[p][ct]) {if(dis[p][ct]<dis[q[t].w][q[t].c]) {t=(t+100000-1)%100000; q[t].w=p; q[t].c=ct; pd[p][ct]=1; } else {q[w].w=p; q[w].c=ct; pd[p][ct]=1; w=(w+1)%100000;} } } if(ct+1<=K&&dis[p][ct+1]>dis[x][ct]) {dis[p][ct+1]=dis[x][ct]; if(!pd[p][ct+1]) {if(dis[p][ct+1]<dis[q[t].w][q[t].c]) {t=(t+100000-1)%100000; q[t].w=p; q[t].c=ct+1; pd[p][ct+1]=1; } else {q[w].w=p; q[w].c=ct+1; pd[p][ct+1]=1; w=(w+1)%100000;} } } } pd[x][ct]=0; } ans=1<<30; for(i=0;i<=K;i++) ans=min(ans,dis[T][i]); printf("%d\n",ans); } int main() { init(); spfa(); return 0; }