bzoj 2763: [JLOI2011]飞行路线

Time Limit: 10 Sec Memory Limit: 128 MB

Submit: 3703 Solved: 1419
[Submit][Status][Discuss]

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

Sample Output

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.

拆点SPFA即可，差点被卡。。。。

#include<bits/stdc++.h>
#define ll long long
#define maxn 10005
#define maxm 100005
using namespace std;
struct node{
    int x,used;
};
int to[maxm],ne[maxm],val[maxm],num=0;
int hd[maxn],n,m,d[maxn][12],S,T,k;
bool iq[maxn][12];

inline void add(int x,int y,int z){
    to[++num]=y,val[num]=z,ne[num]=hd[x],hd[x]=num;
}

inline void spfa(){
    queue<node> q;
    node x;
    memset(d,0x3f,sizeof(d));
    q.push((node){S,0}),iq[S][0]=1,d[S][0]=0;
    
    while(!q.empty()){
        x=q.front(),q.pop(),iq[x.x][x.used]=0;
        for(int i=hd[x.x];i;i=ne[i]){
            if(d[x.x][x.used]+val[i]<d[to[i]][x.used]){
                d[to[i]][x.used]=d[x.x][x.used]+val[i];
                if(!iq[to[i]][x.used]){
                    iq[to[i]][x.used]=1;
                    q.push((node){to[i],x.used});
                }
            }
            if(x.used<k&&d[x.x][x.used]<d[to[i]][x.used+1]){
                d[to[i]][x.used+1]=d[x.x][x.used];
                if(!iq[to[i]][x.used+1]){
                    iq[to[i]][x.used+1]=1;
                    q.push((node){to[i],x.used+1});
                }                                
            }
        }
    }
}

int main(){
    int uu,vv,ww;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&S,&T);
    S++,T++;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&uu,&vv,&ww);
        uu++,vv++;
        add(uu,vv,ww),add(vv,uu,ww);
    }
    
    spfa();
    
    int ans=1<<30;
    for(int i=0;i<=k;i++) ans=min(ans,d[T][i]);
    printf("%d\n",ans);
    return 0;
}