题目链接
BZOJ 1579 道路升级


分层图,可以说是一种构造的手段。
从字面意义上即可看出,分层图就是分层的图。在这道题中,我们把原图复制成k层,在每个相邻的层之间连权值为零的边。之后以第一层的起始点为源,第k层的终止点为汇,求解最短路即可。在求解最短路的过程中,每经过一次权值为零的边,就相当于进行了一次操作。从1层到k层我们最多经过k条权值为零的边,所以保证了题意,求得正解w


AC代码:

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#define N 110000
#define M 1100000
#define K 21
using namespace std;
int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*y;
}
int n=rd(),m=rd(),k=rd(),S=1,T=n;
struct node{
    int to,tar;
    node *nxt;
}table[M],*head[N];
int tot=2;
void ins(int x,int y,int z){
    table[tot].to=y;table[tot].tar=z;
    table[tot].nxt=head[x];head[x]=&table[tot++];
    return;
}
struct __node{
    int first,second,dis;
    __node (int a=0,int b=0,int c=0):first(a),second(b),dis(c){}
    friend bool operator < (__node a,__node b){
        return a.dis>b.dis;
    }
};
priority_queue<__node>Q;
int dis[N][K],vis[N][K];
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[S][0]=0;Q.push((__node){S,0,0});
    while(!Q.empty()){
        int f=Q.top().first,d=Q.top().second;Q.pop();
        for(node *i=head[f];i!=NULL;i=i->nxt){
            int t=i->to,l=i->tar;
            if(dis[t][d]>dis[f][d]+l){
                dis[t][d]=dis[f][d]+l;
                Q.push((__node){t,d,dis[t][d]});
            }
            if(d+1<=k&&dis[t][d+1]>dis[f][d]){
                dis[t][d+1]=dis[f][d];
                Q.push((__node){t,d+1,dis[t][d+1]});
            }
        }
    }
    return;
}
int main(){
    for(int i=0;i<n;i++)head[i]=NULL;
    for(int i=0;i<m;i++){
        int a=rd(),b=rd(),c=rd();
        ins(a,b,c);
        ins(b,a,c);
    }
    spfa();
    printf("%d\n",dis[T][k]);
}

血まみれからの方がさ,勝つ時にはカッコイイだろう.