luogu_4568: 飞行路线

洛谷4568: 飞行路线

题意：

• 给定一张无向图有(n)个点编号为(0)到(n-1)。共有(m)条边，每条边有一个边权。
• 可以选择(k)条边将边权改变为(0)，给定起点和终点，问从起点到终点的路径的最小边权和为多少。

输入描述:

• 第一行输入三个整数(n,m,k)，分别表示点数，边数，(k)。
• 第二行输入两个整数(s,t)表示起点和终点。
• 接下来有(m)行，每行输入(x,y,z)表示从(x)到(y)有边权为(z)的边。
• 数据范围
  • (nleq10^4,mleq5*10^4,kleq10,zleq10^3)

输出描述：

• 输出一个整数表示答案。

思路：

• 分层图模板题。
• 以样例为例：

• 建完图后跑最短路即可
• 建完分层图后边数和点数的计算问题：
  • 点数: 每一层点有(n)个点，一共建立(k)层图，所以总点数为(n*k)。
  • 边数: 每一层图有(m)条边，那么总共有(k*m)条边，相邻两层相互连边有(k-1)个中间层，所以总边数为(k*m)条边。无向图开两倍即可。
• 同时防止毒瘤数据，每层终点连边，解决在(k)还没用完时就到达终点的情况。
• 所以这时候点数(+n)，边数(+m)
• (Hint): 这里的无向图双向连边是指一层内部双向连边，而层与层之间只能单向连边。

代码：

#include<bits/stdc++.h>
#define PII pair<int, int>
using namespace std;

const int maxn = (1e4+10) * 11;
const int maxm = 1e6 + 10 + 5e4 + 10;

int n, m, k, s, t;

int head[maxn], ver[maxm<<1], nex[maxm<<1], edge[maxm<<1], tot;
inline void add_edge(int x, int y, int z){
    ver[++tot] = y; edge[tot] = z;
    nex[tot] = head[x]; head[x] = tot;
}

int dist[maxn];
bool v[maxn];
void dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, s});
    while(q.size())
    {
        int x = q.top().second; q.pop();
        if(v[x]) continue;
        v[x] = 1;
        for(int i = head[x]; i; i = nex[i])
        {
            int y = ver[i], z = edge[i];
            if(dist[y] > dist[x] + z)
            {
                dist[y] = dist[x] + z;
                q.push({dist[y], y});
            }
        }

    }
}

int main()
{
    scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
    s++; t++;
    for(int i = 1, x, y, z; i <= m; i++)
    {
        scanf("%d%d%d", &x, &y, &z); x++, y++;
        add_edge(x, y, z); add_edge(y, x, z);
        for(int j = 1; j <= k; j++)
        {
            //相互两层之间连边
            add_edge(x+(j-1)*n, y+j*n, 0);
            add_edge(y+(j-1)*n, x+j*n, 0);
            //一层中内部连边
            add_edge(x+j*n, y+j*n, z);
            add_edge(y+j*n, x+j*n, z);
        }
    }

    //防止毒瘤数据, k次机会还没用完就到了终点
    for(int i = 1; i <= k; i++)
        add_edge(t+(i-1)*n, t+i*n, 0); //每层之间的终点连边
    dijkstra();
    cout << dist[t+k*n] << endl;
    return 0;
}