BZOJ 2763 [JLOI2011]飞行路线

BZOJ 2763 [JLOI2011]飞行路线

1579: [Usaco2009 Feb]Revamping Trails 道路升级

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 n 个城市设有业务，设这些城市分别标记为 0 到 n-1 ，一共有 m 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 k 种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

本题是一个分层图最短路模型。

何为分层图最短路？

以本题为例，条件可知我们共有K次机会免费。

可以相当于DP，设一个Dis[i][j];表示用了j次机会到达i点的最小花费(长度)

对于(u,v)边来讲

每次更新

1.该条边不免费 dis[e[i].to][j]=min{dis[x][j]+e[i].v}

2.该条边免费 dis[e[i].to][j+1]=min(dis[x][j]) （不算此次边权）
、
为什么叫分层图呢？我们可以相当于每一次免费都是一层，

对于处于k层的某点u来说，

1.u与k层它所连的所有点相连，所连边权为v

2.u与k+1层它所连的所有点相连，所连边权为0（免费）

然后跑最短路算法即可

BZOJ 2763

CODE：

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
const int N = 10010;
const int M = 50010;
struct edge{
    int to,next,v;
}e[M*2];
struct heap{
    int name,v,tot; 
    bool operator < (const heap m) const{
        return v>m.v;
    }
};
std::priority_queue<heap> q;
int last[N],cnt,n,m,k,dis[12][N],s,t,v[12][N];
inline int add(int x,int y,int z){
    cnt++;
    e[cnt].next=last[x],last[x]=cnt;
    e[cnt].to=y,e[cnt].v=z;
}
inline int Dijsktra (int s,int t){
    memset(dis,0x3f,sizeof(dis));
    q.push((heap){s,0,0});
    dis[0][s]=0;
    while(!q.empty()){
        heap tmp=q.top();q.pop();
        if(v[tmp.tot][tmp.name]) continue;
        int l=tmp.tot,x=tmp.name;
        v[l][x]=1;
        for(int i=last[x];i;i=e[i].next){
            if(dis[l][e[i].to]>dis[l][x]+e[i].v){
                dis[l][e[i].to]=dis[l][x]+e[i].v;
                q.push((heap){e[i].to,dis[l][e[i].to],l});
            }
            if(dis[l+1][e[i].to]>dis[l][x]&&l+1<=k){
                dis[l+1][e[i].to]=dis[l][x];
                q.push((heap){e[i].to,dis[l+1][e[i].to],l+1});
            }
        }
    }
    return dis[k][t];
}
int main (){
    scanf("%d %d %d",&n,&m,&k);
    scanf("%d %d",&s,&t);
    s++,t++;
    for(int i=1;i<=m;++i){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        x+=1,y+=1;
        add(x,y,z);
        add(y,x,z);
    }
    int ans=Dijsktra(s,t);
    printf("%d",ans);
    return 0;
}

BZOJ 1579

CODE :

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
const int N = 10010;
const int M = 50010;
struct edge{
    int to,next,v;
}e[M*2];
struct heap{
    int name,v,tot; 
    bool operator < (const heap m) const{
        return v>m.v;
    }
};
std::priority_queue<heap> q;
int last[N],cnt,n,m,k,dis[22][N],s,t,v[22][N];
inline int add(int x,int y,int z){
    cnt++;
    e[cnt].next=last[x],last[x]=cnt;
    e[cnt].to=y,e[cnt].v=z;
}
inline int Dijsktra (int s,int t){
    memset(dis,0x3f,sizeof(dis));
    q.push((heap){s,0,0});
    dis[0][s]=0;
    while(!q.empty()){
        heap tmp=q.top();q.pop();
        if(v[tmp.tot][tmp.name]) continue;
        int l=tmp.tot,x=tmp.name;
        v[l][x]=1;
        for(int i=last[x];i;i=e[i].next){
            if(dis[l][e[i].to]>dis[l][x]+e[i].v){
                dis[l][e[i].to]=dis[l][x]+e[i].v;
                q.push((heap){e[i].to,dis[l][e[i].to],l});
            }
            if(dis[l+1][e[i].to]>dis[l][x]&&l+1<=k){
                dis[l+1][e[i].to]=dis[l][x];
                q.push((heap){e[i].to,dis[l+1][e[i].to],l+1});
            }
        }
    }
    return dis[k][t];
}
int main (){
    scanf("%d %d %d",&n,&m,&k);
    s=1,t=n; 
    for(int i=1;i<=m;++i){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    int ans=Dijsktra(s,t);
    printf("%d",ans);
    return 0;
}