題目鏈接：點(diǎn)擊查看
題目大意：給出 n 個(gè)點(diǎn)，每個(gè)點(diǎn)都有一個(gè)權(quán)值 a[ i ]，且每個(gè)點(diǎn)可以到達(dá) ( i - a[ i ]?) 和 ( i + a[ i ] ) 兩個(gè)位置，花費(fèi)為 1，問每個(gè)點(diǎn)到達(dá)與其本身奇偶不同的點(diǎn)的最小花費(fèi)是多少
題目分析：看到網(wǎng)上那么多假算法的題解真的人傻了，寫了個(gè) spfa 恩說是 bfs ，不過這題好像真的沒法卡掉 spfa，但也不能指鹿為馬吧
因?yàn)槊總€(gè)偶數(shù)權(quán)值的點(diǎn)的終點(diǎn)是奇數(shù)權(quán)值，同理每個(gè)奇數(shù)權(quán)值的點(diǎn)的終點(diǎn)是偶數(shù)權(quán)值，如此一來可以反向建邊，按照奇偶分別跑一次多源起點(diǎn)的最短路就是答案了
為了更好的理解這個(gè)模型，其實(shí)也可以加入一個(gè)虛擬點(diǎn) X 方便理解，這里以一種情況舉例，假設(shè)所有的奇數(shù)權(quán)值都需要求到偶數(shù)權(quán)值的最短路，那么我們不妨令所有的偶數(shù)權(quán)值都向這個(gè)虛擬點(diǎn)連邊，權(quán)值為 0，這樣當(dāng)奇數(shù)權(quán)值的點(diǎn)找到匹配的偶數(shù)權(quán)值的點(diǎn)后，自然可以不用花費(fèi)也能到達(dá)點(diǎn) X，這樣問題就轉(zhuǎn)換成了：多個(gè)起點(diǎn)，一個(gè)終點(diǎn)的最短路模型，相應(yīng)的解決辦法就是將原圖方向取反然后以終點(diǎn)為起點(diǎn)跑單源最短路了
代碼：
// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;//頂點(diǎn)數(shù) const int M=1e6+100;//邊數(shù) struct Edge
{int to,w,next;
}edge[M];int head[N],d[N],a[N],ans[N],cnt,n;//鏈?zhǔn)角跋蛐?bool vis[N];void addedge(int u,int v,int w)
{edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}struct Node
{int to,w;Node(int TO,int W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;}
};void Dijkstra(int flag)
{priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(d,inf,sizeof(d));for(int i=1;i<=n;i++)if(a[i]%2==flag){q.push(Node(i,0));d[i]=0;}while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;int w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}}for(int i=1;i<=n;i++)if(a[i]%2!=flag&&d[i]!=inf)ans[i]=d[i];
}void init()
{memset(ans,-1,sizeof(ans));memset(head,-1,sizeof(head));cnt=0;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",a+i);if(i-a[i]>=1)addedge(i-a[i],i,1);if(i+a[i]<=n)addedge(i+a[i],i,1);}Dijkstra(0);Dijkstra(1);for(int i=1;i<=n;i++)printf("%d ",ans[i]);puts("");return 0;
}
?
總結(jié)
以上是生活随笔 為你收集整理的CodeForces - 1272E Nearest Opposite Parity(多源起点的最短路) 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
