算法1,分层图的暴力构建

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 60*60 ,M=250010;
typedef pair<int, int> PII;

int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
int n,m,k;

void add(int a, int b, int c) 
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra()  
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    memset(h, -1, sizeof h);
    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);

        for(int j=1;j<=k;j++){  
            add(u+j*n,v+j*n,w);
            add(v+j*n,u+j*n,w);    //同层构建

            add(u+j*n-n,v+j*n,w/2);   //不同层构建
            add(v+j*n-n,u+j*n,w/2);
        }
    }
    dijkstra();
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;i++){
        ans=min(ans,dist[n+i*n]);
    }
    printf("%d",ans);
}

具体还有另外一种用动态规划思想的构建方式可以参考这篇博客，讲的很详细

https://www.cnblogs.com/ldyzzz/p/17632253.html