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

Description

每天,农夫John需要经过一些道路去检查牛棚N里面的牛.

农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M. 道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N).

John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i 走到P１_i

他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K (1 <= K <= 20)条路经，将它们所须时间减为０．

帮助FJ选择哪些路经需要更新使得从１到N的时间尽量少.

Input

* 第一行: 三个空格分开的数: N, M, 和 K * 第2..M+1行: 第i+1行有三个空格分开的数：P1_i, P2_i, 和 T_i

Output

* 第一行: 更新最多Ｋ条路经后的最短路经长度．

Sample Input

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Sample Output

HINT

K是1; 更新道路3->4使得从３到４的时间由１００减少到０. 最新最短路经是1->3->4,总用时为１单位. N<=10000

————————————————————————————————

感觉还是有必要发一篇题解吧因为网上的代码都好复杂QAQ——其实只需要五六十行的样子

我们只要在正常的dijkstra上把数组d【i】（表示距离）转换成d【i】【j】表示从1走到i 在使用了 j 次变 0 技能后的最短路

之后的操作就和正常的dijkstra一样了每次取最近的出堆更新其他结点就好了等到点n 出堆的时候就是答案了

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int N=,inf=0x7f7f7f7f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k;

int d[N][];

struct node{

    int d,h,pos;

    bool operator <(const node& x)const{return x.d<d;}

};

priority_queue<node>q;

int first[N],cnt;

struct pos{int to,next,w;}e[*N];

void ins(int a,int b,int w){e[++cnt]=(pos){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

int dj(){

    memset(d,0x7f,sizeof(d));

    for(int i=;i<=k;i++) d[][i]=;

    q.push((node){,,});

    while(!q.empty()){

        node p=q.top(); q.pop();

        if(d[p.pos][p.h]!=p.d) continue;

        if(p.pos==n) return p.d;

        int x=p.pos,h=p.h;

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(d[now][h]>d[x][h]+e[i].w) d[now][h]=d[x][h]+e[i].w,q.push((node){d[now][h],h,now});

            if(h<k&&d[now][h+]>d[x][h]) d[now][h+]=d[x][h],q.push((node){d[now][h+],h+,now});

        }

    }

    return d[n][k];

}

int main()

{

    int x,y,v;

    n=read(); m=read(); k=read();

    for(int i=;i<=m;i++) x=read(),y=read(),v=read(),insert(x,y,v);

    printf("%d\n",dj());

    return ;

}

巴特西

bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级——分层图+dijkstra