lazy running(最短路)

题意: 一个环上有四个点，从点2出发回到起点，走过的距离不小于K的最短距离是多少 \(K <= 10^{18} 1 <= d <= 30000\)

看完这道题，觉得这是个智力题，想了一想，无从下手啊

每次总是看完题解，就豁然开朗

其实之前做过一个类似的题，题目

但是根本想不到第一步, 选2w来转换啊，而且也不知道正确性啊

这类题要仔细理解一番

#include<bits/stdc++.h>

#define LL long long

#define P pair<int,int>

using namespace std;

const LL inf = 1e18;

const int N = 6e4 + 10;

int g[4][4];

int mod;

LL K;

LL dis[4][N];

int inq[4][N];

void spfa(){

    for(int i = 0;i < 4;i++){

        for(int j = 0;j < mod;j++) {

            dis[i][j] = inf,inq[i][j] = 0;

        }

    }

    queue<P> q;

    dis[1][0] = 0,inq[1][0] = 0;

    q.push(P(1,0));

    while(!q.empty()){

        P cur = q.front();q.pop();

        for(int i = -1;i <= 2;i+=2){

            int x = (cur.first + i + 4)%4, y = (cur.second + g[cur.first][x])%mod;

            if(dis[x][y] > dis[cur.first][cur.second] + g[cur.first][x]){

                dis[x][y]= dis[cur.first][cur.second] + g[cur.first][x];

                if(!inq[x][y]){

                    inq[x][y] = 1;

                    q.push(P(x,y));

                }

            }

        }

    }

}

int main()

{

    int T;

    cin>>T;

    while(T--){

        cin>>K;

        for(int i = 0;i < 4;i++) {

            scanf("%d",&g[i][(i+1)%4]);

            g[(i+1)%4][i] = g[i][(i+1)%4];

        }

        mod = 2 * min(g[0][1],g[1][2]);

        spfa();

        LL ans = 2e18;

        for(int i = 0;i < mod;i++){

            LL d = K - dis[1][i];

            ans = min(ans, dis[1][i] + (d + mod - 1) / mod * mod);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

多校4 lazy running (最短路)

lazy running(最短路)

题意: 一个环上有四个点，从点2出发回到起点，走过的距离不小于K的最短距离是多少 \(K <= 10^{18} 1 <= d <= 30000\)

最新文章

热门文章