bzoj 2763: [JLOI2011]飞行路线 分层图

题目链接

n个点m条路， 每条路有权值，  给出起点和终点， 求一条路使得权值最小。可以使路过的路中， k条路的权值忽略。

其实就是多一维， 具体看代码

#include<bits/stdc++.h>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, a, n) for(int i = a; i<n; i++)

#define ull unsigned long long

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

const int maxn = 5e4+;

int dis[][], in[][], num, head[maxn*];

int n, m, k, s, t;

struct edge

{

    int to, nextt, w;

}e[maxn*];

struct node

{

    int u, x;

    node(){}

    node(int u, int x):u(u),x(x){}

};

void init() {

    mem1(head);

    num = ;

}

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

    e[num].to = v;

    e[num].nextt = head[u];

    e[num].w = w;

    head[u] = num++;

}

queue <node> q;

int dij() {

    mem2(dis);

    q.push(node(s, ));

    dis[][s] = ;

    in[][s] = ;

    while(!q.empty()) {

        node tmp = q.front(); q.pop();

        int u = tmp.u, x = tmp.x;

        in[x][u] = ;

        for(int i = head[u]; ~i; i = e[i].nextt) {

            int v = e[i].to;

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

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

                if(!in[x][v]) {

                    in[x][v] = ;

                    q.push(node(v, x));

                }

            }

        }

        if(x<k) {

            x++;

            for(int i = head[u]; ~i; i = e[i].nextt) {

                int v = e[i].to;

                if(dis[x][v]>dis[x-][u]) {

                    dis[x][v] = dis[x-][u];

                    if(!in[x][v]) {

                        in[x][v] = ;

                        q.push(node(v, x));

                    }

                }

            }

        }

    }

    int ans = inf;

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

        ans = min(ans, dis[i][t]);

    return ans;

}

int main()

{

    int x, y, z;

    cin>>n>>m>>k>>s>>t;

    init();

    while(m--) {

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

        add(x, y, z);

        add(y, x, z);

    }

    int ans = dij();

    cout<<ans<<endl;

    return ;

}