【luogu P4568 [JLOI2011]飞行路线】题解

题目链接：https://www.luogu.org/problemnew/show/P4568

卡了一晚上，算是分层图最短路的模板。注意卡SPFA，所以我写了个SLF优化。

同时 AC400祭！~

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ri register

using namespace std;

const int maxn = 200000 + 10;

const int inf = 2147483647;

inline int read()

{

    int k=0,f=1;

    char c=getchar();

    while(!isdigit(c))

    {

        if(c=='-')f=-1;

        c=getchar();

    }

    while(isdigit(c))

    {

        k=(k<<1)+(k<<3)+c-48;

        c=getchar();

    }

    return k*f;

}

int n, m, k, s, end, dis[maxn][20];

bool vis[maxn][20];

struct edge{

    int from, len, to, next;

}e[maxn<<2];

int head[maxn], cnt = 0;

struct que{

    int a, b;

};

deque<que> q;

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

{

    e[++cnt].from = u;

    e[cnt].to = v;

    e[cnt].len = w;

    e[cnt].next = head[u];

    head[u] = cnt;

}

inline void SPFA()

{

    memset(dis, 127, sizeof(dis));

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

    q.push_back((que){s,0});

    dis[s][0] = 0;

    vis[s][0] = 1;

    while(!q.empty())

    {

        que now = q.front(); q.pop_front();

        vis[now.a][now.b] = 0;

        for(ri int i = head[now.a]; i != -1; i = e[i].next)

        {

            if(dis[e[i].to][now.b] > dis[now.a][now.b] + e[i].len)

            {

                dis[e[i].to][now.b] = dis[now.a][now.b] + e[i].len;

                if(vis[e[i].to][now.b] == 0)

                {

                    vis[e[i].to][now.b] = 1;

                    if(q.empty() || dis[e[i].to][now.b] > dis[q.front().a][now.b])

                          q.push_back((que){e[i].to, now.b});

                    else

                    q.push_front((que){e[i].to, now.b});

                }

            }

            if(now.b + 1 <= k)

            {

                if(dis[e[i].to][now.b + 1] > dis[now.a][now.b])

                {

                    dis[e[i].to][now.b + 1] = dis[now.a][now.b];

                    if(vis[e[i].to][now.b + 1] == 0)

                    {

                    		vis[e[i].to][now.b + 1] = 1;

                    		if(q.empty() || dis[e[i].to][now.b] > dis[q.front().a][now.b + 1])

                        q.push_back((que){e[i].to, now.b + 1});

                        else

                        q.push_front((que){e[i].to, now.b + 1});

                    }

                }

            }

        }

    }

}

int main()

{

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    memset(head, -1, sizeof(head));

    n = read(); m = read(); k = read(); s = read(); end = read();

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

    {

        int u, v, w;

        u = read(); v = read(); w = read();

        add(u, v, w); add(v, u, w);

    }

    SPFA();

    printf("%d",dis[end][k]);

    return 0;

}

巴特西

【luogu P4568 [JLOI2011]飞行路线】题解

最新文章

热门文章

巴特西

【luogu P4568 [JLOI2011]飞行路线】 题解

最新文章

热门文章

【luogu P4568 [JLOI2011]飞行路线】题解