Codeforces 1272E (Nearest Opposite Parity,反向建边)

题意：给你n个数，每个数的值为a[i],每个点可以从i这号点跳转至(i - a[i]) 或 (i + a[i])点，点的范围为[1,n],然后问的是从偶数点跳至奇数点，从奇数点跳至偶数点的最少次数是多少?

解答：这个题很不错，难度系数1900。让我对反向建边有了一定的认识。

为什么需要反向建边呢？因为正向建边无法很好地做到更新当前自身u的情况,但却可以更新v最小的情况(可是所有v中的最小情况明明应该是u的最小情况，这就是正向的缺点)。而可以通过反向建边，不断更新，最后更新到目标点，该目标点已经是最优的情况了。

关于超级源点和超级汇点：我们把所有奇数点与超级源点0相连，偶数点与超级汇点n+1相连，相连距离为0，然后分别跑Dijkstra.

Dijkstra1(以奇数点为起点)跑出来的结果是偶数的最小情况，如果是INF那就说明转换不到输出-1;

Dijkstra2(以偶数点为起点)跑出来的结果是奇数的最小情况，如果是INF那就说明转换不到输出-1;

最后看自己的奇偶性输出自己的情况就行了。

#include<bits/stdc++.h>

#define ll long long

#define white 0

#define black 1

#define grey  2

#define endl '\n'

#define INF 0x3f3f3f3f3f

#define IO ios::sync_with_stdio(false);cin.tie(0);

using namespace std;

const int maxn=3e5+;

int tot,head[maxn];

struct E{

    int to,next,w;

}edge[maxn<<];

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

    edge[tot].to=v;

    edge[tot].w=w;

    edge[tot].next=head[u];

    head[u]=tot++;

}

ll d1[maxn],d2[maxn];ll color[maxn];

priority_queue<pair<ll,ll> >q;

ll n,a[maxn];

void Dijkstra(ll s,ll *d){

    for(ll i=;i<=n;i++) d[i]=INF,color[i]=white;

    d[s]=;

    q.push(make_pair(,s));

    color[s]=grey;

    while(!q.empty()){

        pair<ll,ll> f=q.top();

        q.pop();

        ll u=f.second;

        color[u]=black;

        if(d[u]<f.first*(-)) continue;

        for(ll i=head[u];i!=-;i=edge[i].next){

            int v=edge[i].to;

            if(color[v]==black) continue;

            if(d[v]>d[u]+edge[i].w){

                d[v]=d[u]+edge[i].w;

                q.push(make_pair(d[v]*(-),v));

                color[v]=grey;

            }

        }

    }

}

signed main(){

    cin>>n;memset(head,-,sizeof(head));

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

        cin>>a[i];

        if(a[i]%==) add(,i,);

        if(a[i]%==) add(n+,i,);

        if(i+a[i]<=n) add(i+a[i],i,);

        if(i-a[i]>=) add(i-a[i],i,);

    }

    Dijkstra(,d1);

    Dijkstra(n+,d2);

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

        if(a[i]%==){

            if(d2[i]==INF) cout<<"-1"<<" ";

            else cout<<d2[i]<<" ";

        }else{

            if(d1[i]==INF) cout<<"-1"<<" ";

            else cout<<d1[i]<<" ";

        }

    }

    cout<<endl;

}