碼蹄集OJ-夏日漫步
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010],dis[200010],qaq[1000010];
vector<int>son[200010];
int que[200010];
int main( )
{memset(qaq,-1,sizeof(qaq));memset(dis,-1,sizeof(dis));cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=n;i>0;i--){if(qaq[a[i]]!=-1){son[i].push_back(qaq[a[i]]);}qaq[a[i]]=i;}for(int i=1;i<n;i++){son[i].push_back(i+1);son[i+1].push_back(i); }int tail=2;que[1]=1;dis[1]=0;for(int i=1;i<=n;i++){int cur=que[i];for(auto v:son[cur]){if(dis[v]==-1){dis[v]=dis[cur]+1;que[tail]=v;tail++;}}}cout<<dis[n]<<endl;return 0;
}題目表示從頭開始每一個節點可以依次相連，構成一個無向圖，而且跟據每一個節點的權值可以完善這個圖，將權值相同的節點相連，這樣題目就抽象成了圖論。
由于節點少邊多，所以想到運用鄰接表進行BFS搜索。
構造鄰接表：
for(int i=n;i>0;i--){if(qaq[a[i]]!=-1){son[i].push_back(qaq[a[i]]);}qaq[a[i]]=i;}for(int i=1;i<n;i++){son[i].push_back(i+1);son[i+1].push_back(i); }qaq數組存儲權值的節點值，初始化時通過memset函數將數組初始化成-1，從后向前遍歷數組，如果qaq被賦值，說明在這個節點后有節點的權值與這個節點相同，將這個節點的孩子節點賦值為上一個節點值。（這種遍歷方式實現了題目中人只能向后走，而且只能走到與到此節點下一個權值相同的節點）。接著將1到n個節點依次相連就行了，鄰接表就構造好了。
BFS搜索過程，尋找最優路徑。
int tail=2;que[1]=1;dis[1]=0; for(int i=1;i<=n;i++){int cur=que[i];for(auto v:son[cur]){if(dis[v]==-1){dis[v]=dis[cur]+1;que[tail]=v;tail++;}}}令隊列中存入的第一個根節點是1，從頭開始遍歷隊列中每一個節點，隊列中依次存入的是根節點的子節點。dis[i]存儲的是節點i到節點1的距離，所以最后輸出的是dis[n]。開始時，將dis數組初始化成-1，令dis[1]為0。在遍歷隊列中節點時，由于v是cur的孩子節點，所以dis[v]的值要在dia[cur]的基礎下加1。為了尋找最優路徑，要處理一種情況，在當前節點的孩子節點也是當前節點的根節點的孩子節點時，不對這個子節點進行路徑更改，也不將子節點入隊。也就是避免重復入隊和保證第一次到達某個節點時的路徑就是最短路徑。
BFS 的核心特性就是：
第一次訪問到某個節點時的路徑長度，就是最短路徑長度。
