正題

---

題目大意

$n$個點，每個點可以走到$[a_i,n]$，每個點可以從$[b_i,n]$到達。

求$di{s}_{i,j}?(i+j)$的異或和

---

解題思路

首先我們可以知道肯定是先往后跳再往前走最優，因為如果先往前再往后最優的話顯然可以直接往后跳。

所以我們先計算往前走的步數，枚舉一個終點，然后一層一層擴展即可

之后考慮往后走，我們可以用并查集來，從步數少的枚舉到步數大的，然后用并查集進行往后擴展，之后不斷更新最短距離

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=6100; int n,a[N],b[N],dis[N][N],fa[N],ans; bool v[N]; vector<int> q[N]; int find(int x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} int main() {scanf("%d",&n);for(int i=2;i<=n;i++)scanf("%d",&a[i]);for(int i=2;i<=n;i++)scanf("%d",&b[i]);memset(dis,0x3f,sizeof(dis));for(int i=1;i<=n;i++){dis[i][i]=0;int j=i-1,k=b[i],w=1;while(j){int z=k;for(;j>=z;j--){dis[j][i]=w;k=min(k,b[j]);}w++;}}a[1]=1;for(int i=1;i<=n;i++){for(int j=0;j<=n;j++){q[j].clear();fa[j]=j;v[j]=0;}for(int j=i;j<=n;j++)q[dis[i][j]].push_back(j);for(int j=0;j<=n;j++)for(int k=0;k<q[j].size();k++){int p=q[j][k];if(v[p])continue;v[p]=1;for(p=find(p);p>=a[q[j][k]];p=find(p)){if(dis[i][q[j][k]]+1<dis[i][p])dis[i][p]=dis[i][q[j][k]]+1;q[dis[i][p]].push_back(p);fa[p]=find(p-1);}}}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans^=dis[i][j]*(i+j);printf("%d",ans); }

總結

以上是生活随笔為你收集整理的nssl1454-最短路【并查集,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。