链接：

https://codeforces.com/contest/1272/problem/E

题意：

You are given an array a consisting of n integers. In one move, you can jump from the position i to the position i−ai (if 1≤i−ai) or to the position i+ai (if i+ai≤n).

For each position i from 1 to n you want to know the minimum the number of moves required to reach any position j such that aj has the opposite parity from ai (i.e. if ai is odd then aj has to be even and vice versa).

思路：

写了好久DFS发现有环不能处理。。看了大佬博客才懂。

考虑从a开始的最短路，计算的是a到x的最短路。

反向建图，跑出来的最短路，就是他能到达的点往自己的最短路。

建立两个新点，分别连奇数点和偶数点，跑最短路。

代码：

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

const int MAXN = 2e5+10;

vector<int> G[MAXN];

int a[MAXN], ans[MAXN], dis[MAXN], vis[MAXN];

int n;

void SPFA(int s)

{

    queue<int> que;

    for (int i = 1;i <= n+2;i++)

        dis[i] = INF, vis[i] = 0;

    que.push(s);

    dis[s] = 0;

    vis[s] = 1;

    while(!que.empty())

    {

        int u = que.front();

        que.pop();

        vis[u] = 0;

        for (int i = 0;i < (int)G[u].size();++i)

        {

            int node = G[u][i];

            if (dis[node] > dis[u]+1)

            {

                dis[node] = dis[u]+1;

                if (vis[node] == 0)

                {

                    que.push(node);

                    vis[node] = 1;

                }

            }

        }

    }

}

int main()

{

    cin >> n;

    for (int i = 1;i <= n;++i)

        cin >> a[i];

    for (int i = 1;i <= n;++i)

    {

        if (i-a[i] >= 1)

            G[i-a[i]].push_back(i);

        if (i+a[i] <= n)

            G[i+a[i]].push_back(i);

    }

    for (int i = 1;i <= n;++i)

    {

        if (a[i]%2 == 1)

            G[n+1].push_back(i);

        else

            G[n+2].push_back(i);

    }

    SPFA(n+1);

    for (int i = 1;i <= n;++i)

        if (a[i]%2 == 0) ans[i] = dis[i];

    SPFA(n+2);

    for (int i = 1;i <= n;++i)

        if (a[i]%2 == 1) ans[i] = dis[i];

    for (int i = 1;i <= n;++i)

        cout << ((ans[i] == INF) ? -1 : ans[i]-1) << ' ' ;

    cout << endl;

    return 0;

}

巴特西

Codeforces Round #605 (Div. 3) E. Nearest Opposite Parity（最短路）

链接：

题意：

思路：

代码：

最新文章

热门文章