分层图最短路

发布于 2018-03-11  363 次阅读


定义

分层图最短路问题,一般是指我们在可以进行分层的图上进行最短路。
一般模型是:
在图上,有k次机会可以直接通过一条边,问起点与终点之间的最短路径。
题目链接

分析

其实这一题我们用动态规划的思想看,用dist[i][k]表示免费了k次的最短路径
详细的转移请参考代码
然后跑最短路即可。

代码

/*
做这一题的时候不知道怎么回事,用指针就疯狂WA,最后写了数组才过。。。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <algorithm>

const int MAXN = 10000 + 5;
const int MAXM = 50000 + 5;
const int MAXK = 10 + 5;

int N,M,K,S,T;
int dist[MAXN][MAXK];//dist[i][k]表示第k层结点i到起点的最短距离
int head[MAXN],cnt;
bool inQueue[MAXN][MAXK];//inQueue[i][k]表示第k层的结点i是否在队列

struct Edge{
    int to,w,next;
}e[MAXM * 2];

inline void add(int u,int v,int w){
    e[++cnt].w = w;e[cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
}

void spfa(){
    memset(dist,0x7f,sizeof(dist));
    memset(inQueue,false,sizeof(inQueue));
    std::queue<std::pair<int,int> > q;
    q.push(std::make_pair(S,0));
    inQueue[S][0] = true;
    dist[S][0] = 0;
    while(!q.empty()){
        int v = q.front().first;
        int step = q.front().second;
        q.pop();
        inQueue[v][step] = false;
        for(int i = head[v];i;i = e[i].next){
            int to = e[i].to;
            if(dist[v][step] + e[i].w < dist[to][step]){ //同层转移
                dist[to][step] = dist[v][step] + e[i].w;
                if(!inQueue[to][step]){
                    inQueue[to][step] = true;
                    q.push(std::make_pair(to,step));
                }
            }
            if(dist[v][step] < dist[to][step+1] && step < K){ //异层转移
                dist[to][step+1] = dist[v][step];
                if(!inQueue[to][step+1]){
                    inQueue[to][step+1]=1;
                    q.push(std::make_pair(to,step + 1));
                }
            }
        }
    }
    int ans = INT_MAX;
    for(int i = 0;i <= K;i++) //统计答案
        ans = std::min(ans,dist[T][i]);
    printf("%d",ans);
}

int main(){
    scanf("%d%d%d%d%d",&N,&M,&K,&S,&T);
    for(int i = 1;i <= M;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    spfa();
    return 0;
}


一个OIer。