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

堆优化的dijkstra。

把一个点拆成k个。

日常空间要开炸一次。。

//Twenty

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

typedef long long LL;

using namespace std;

const int maxn=+;

const int maxm=*+;

int n,m,k,fir[maxn],nxt[maxm],to[maxm],vis[maxn][],dis[maxn][],ecnt;

LL val[maxm],ans;

struct node {

    int id,k;

    LL d;

    friend bool operator <(const node &A,const node &B) {

        return A.d>B.d;

    }

    node(){}

    node(int id,LL d,int k):id(id),d(d),k(k){}

};

priority_queue<node>que;

void add(int u,int v,int w) {

    nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;

    nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;

}

void dijkstra() {

    memset(dis,,sizeof(dis));

    dis[][]=;

    que.push(node(,,));

    while(!que.empty()) {

        node x=que.top();

        vis[x.id][x.k]=;

        que.pop();

        if(x.id==n) {ans=x.d; break;}

        for(int i=fir[x.id];i;i=nxt[i]) {

            if(!vis[to[i]][x.k]&&x.d+val[i]<dis[to[i]][x.k]) {

                dis[to[i]][x.k]=x.d+val[i];

                que.push(node(to[i],x.d+val[i],x.k));

            }

            if(x.k+<=k&&!vis[to[i]][x.k+]&&x.d<dis[to[i]][x.k+]) {

                dis[to[i]][x.k+]=x.d;

                que.push(node(to[i],x.d,x.k+));

            }

        }

     }

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=m;i++) {

        int x,y; LL z;

        scanf("%d%d%lld",&x,&y,&z);

        add(x,y,z);

    }

    dijkstra();

    printf("%lld\n",ans);

    return ;

}