P4568 [JLOI2011]飞行路线

思路

套路题

建出k+1分层图，从上一层走到下一层代表坐了一次免费航线，跑最短路即可

注意可能有情况不需要耗完所有k次机会，所以应从每层的终点向下一层终点连一条边权为0的边

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

int u[4000100],v[4000100],w[4000100],fir[4000100],nxt[4000100],cnt,n,m,k,s,t,dis[4000100],vis[4000100];

struct QNode{

    int dis,x;

    bool operator < (const QNode &b) const{

        return dis>b.dis;

    }

};

priority_queue<QNode> q;

void addedge(int ui,int vi,int wi){

    ++cnt;

    u[cnt]=ui;

    v[cnt]=vi;

    w[cnt]=wi;

    nxt[cnt]=fir[ui];

    fir[ui]=cnt;

}

void dij(int s){

    memset(dis,0x3f,sizeof(dis));

    memset(vis,0,sizeof(vis));

    dis[s]=0;

    q.push((QNode){0,s});

    while(!q.empty()){

        QNode u=q.top();

        q.pop();

        if(vis[u.x])

            continue;

        vis[u.x]=true;

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

            if(dis[v[i]]>dis[u.x]+w[i]){

                dis[v[i]]=dis[u.x]+w[i];

                q.push((QNode){dis[v[i]],v[i]});

            }

        }

    }

}

int main(){

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

    scanf("%d %d",&s,&t);

    s++;

    t++;

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

        int a,b,c;

        scanf("%d %d %d",&a,&b,&c);

        a++,b++;

        for(int j=1;j<=k+1;j++){

            addedge(a+(n*(j-1)),b+(n*(j-1)),c);

            addedge(b+(n*(j-1)),a+(n*(j-1)),c);

        }

        for(int j=1;j<=k;j++){

            addedge(a+(n*(j-1)),b+(n*(j)),0);

            addedge(b+(n*(j-1)),a+(n*(j)),0);

        }

    }

    for(int i=1;i<=k;i++)

        addedge(t+(n*(i-1)),t+(n*i),0);

    dij(s);

    printf("%d\n",dis[t+k*n]);

    return 0;

}