CF605E Nearest Opposite Parity【最短路】【多源变单源】【超级源点】

Nearest Opposite Parity

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

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

Input
The first line of the input contains one integer 𝑛 (1≤𝑛≤2e5) — the number of elements in 𝑎.

The second line of the input contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛), where 𝑎𝑖 is the 𝑖-th element of 𝑎.

Output
Print 𝑛 integers 𝑑1,𝑑2,…,𝑑𝑛, where 𝑑𝑖 is the minimum the number of moves required to reach any position 𝑗 such that 𝑎𝑗 has the opposite parity from 𝑎𝑖 (i.e. if 𝑎𝑖 is odd then 𝑎𝑗 has to be even and vice versa) or -1 if it is impossible to reach such a position.

Example
input

10
4 5 7 6 7 5 4 4 6 4

output

1 1 1 2 -1 1 1 3 1 1

题意

一个数组，i位置可以到达i +/- a[ i ] 位置（不越界情况下），问你每个位置要走到一个奇偶性相反的地点最少要走几次

分析【超级源点】【反向思维】

此题是一个比较典型的多源变单源的最短路问题,以奇数为例，要求得某个奇数可以由哪些偶数走过来，就应该以所有的偶数为起点出发，看谁能先到达此奇数点，在使用Dijkstra时，可以把所有的偶数点都放进去，进行扩展。也可以用一个超级源点来连接所有偶数点，在使用Dijkstra时，把此超级源点放进去就行了。然后就跑单源最短路算法，因为每一个奇数点都是由偶数点为起点得出的路径，此时就可以反向思维，是偶数点走到奇数点，且这条路径是最短的 这里我用的是堆优化版的Dijkstra算法。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;
typedef pair<int,int> pii;

int N;
int arr[maxn];
int h[maxn],e[maxn],ne[maxn],idx;
int vis[maxn],dis[maxn],res[maxn];
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dij(int s){
    priority_queue<pii,vector<pii>,greater<pii> > q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis)); dis[s] = 0;
    q.push({0,s});
    while(!q.empty()){
        pii cur = q.top();q.pop();
        int d = cur.first,u = cur.second;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = h[u];i!=-1;i = ne[i]){
            int v = e[i];
            if(d+1<dis[v]){
                dis[v] = d+1;
                q.push({dis[v],v});
            }
        }
    }
}

int main(){
    memset(h,-1,sizeof(h));
    cin>>N;
    for(int i = 0;i<N;i++) scanf("%d",&arr[i]);
    for(int i = 0;i<N;i++){
        if(i-arr[i] >= 0) add(i-arr[i],i);
        if(i+arr[i] < N) add(i+arr[i],i);
        if(arr[i]%2 == 0) add(N+0,i);//N+0 为所有偶数点的超级源点
        if(arr[i]%2 == 1) add(N+1,i);//N+1 为所有奇数点的超级源点
    }
    dij(N+0);
    for(int i = 0;i<N;i++) if(arr[i]%2 == 1) res[i] = dis[i]; //得出来的奇->偶路径复制到结果中
    dij(N+1);
    for(int i = 0;i<N;i++) if(arr[i]%2 == 0) res[i] = dis[i]; //得出来的偶->奇路径复制到结果中
    for(int i = 0;i<N;i++){
        if(res[i]>=0x3f3f3f3f) printf("-1 ");
        else printf("%d ",res[i]-1);//因为加入了超级源点，所以距离-1
    }
    return 0;
}