題目鏈接：點擊查看

題目大意：我們要從左上角走到右下角，只能斜著走，問最少翻轉(zhuǎn)道路的次數(shù)

題目分析：很直白的一個中文題，也沒有多少坑，主要是思路問題，這里先說思路，我們可以將給出的道路建邊，建成一個無向圖，如果每兩個相鄰的頂點之間已經(jīng)有一條路了，那么我們將其權(quán)值設(shè)為0（不用翻轉(zhuǎn)），否則設(shè)為1（需要翻轉(zhuǎn)一次），這樣從點（0,0）跑一邊單源最短路就能求出到點（n,m）的最短路了，也就是題目要求的最少翻轉(zhuǎn)次數(shù)

現(xiàn)在在講一下我做這個題目的心路歷程吧。。畢竟也是搞了一上午的一個題目（我太菜了）

這個題目是zx學(xué)長給掛的一道搜索題，一開始按照zx學(xué)長的思路寫了一發(fā)思維建邊+spfa的代碼，交上去WA了，過了兩個樣例

仔細(xì)一檢查發(fā)現(xiàn)是初始化出了點問題，重新修正后再次提交，T掉了，過了六個樣例

于是我就在計算時間復(fù)雜度，spfa的最差時間復(fù)雜度是O(ve)這個題目的e是4*v，也就是說最差的時間復(fù)雜度到了4*e*e，也就是4*500*500*500*500=2e11。。。emmm，不T才怪，還能過了5個樣例，那前五個樣例應(yīng)該挺水的吧。。

然后就只能中規(guī)中矩的迪杰斯特拉+優(yōu)先隊列優(yōu)化了，這樣的話時間復(fù)雜度下降到了O(nlogn)，差不多是500*500*log(500*500)，大概是500*500*20=5e6，按理說應(yīng)該沒問題了，交上去又T掉了，這個題目在測試時最多有五個樣例，這樣的話5*5e6也才2e7，給了一秒要么是我的常數(shù)太大了，要么就是評測機辣雞，不過還是過掉了7個樣例

最后我在優(yōu)化常數(shù)的道路上越走越遠，一直T一直T，給我T自閉了，然后上網(wǎng)上去搜題解，看到了這個題目可以用搜索寫，于是興致勃勃的去寫了一發(fā)bfs，因為bfs屬于擴展，所以時間復(fù)雜度最壞也才500*500=2e5，肯定穩(wěn)了，寫完過掉樣例后交了一發(fā)，WA掉了。。看了看WA了的樣例，意識到只能用最短路的思想，也就是有點dp的思想，每次都用最優(yōu)解更新每個點的最短路，這樣才能保證跑出來的答案是最優(yōu)解

以上以上，在失敗了那么多次后，我抱著碰碰運氣的心態(tài)，將之前迪杰斯特拉+優(yōu)先隊列的算法改成了迪杰斯特拉+雙端隊列的寫法，這樣不能保證算法的正確性，但是卻能將時間復(fù)雜度下降到O(n)，這樣總的時間復(fù)雜度也是5*500*500=1e6，交了一發(fā)，竟然A掉了，我是這樣分析的（如有錯誤，歡迎指出）：

迪杰斯特拉算法之所以能用優(yōu)先隊列優(yōu)化，是因為每次都需要選更優(yōu)的解來更新當(dāng)前的解才行，而如果該頂點的最優(yōu)解已經(jīng)更新了其他頂點的最短路后，該頂點的其他方案都可以直接跳過了，所以當(dāng)我們在更新完每個點的最短路后，我們判斷一下當(dāng)前加入的邊是0還是1，如果是0的話我們將其添加到隊首，如果是1的話我們將其添加到隊尾，我們優(yōu)先先將權(quán)值為0的邊互相處理完，這樣再來處理權(quán)值為1的邊，這樣也能保證結(jié)果的正確性，相對于優(yōu)先隊列的寫法，雙端隊列的寫法因為每個操作都是O(1)實現(xiàn)，所以省去了優(yōu)先隊列內(nèi)部的logn的時間開銷，所以能把時間復(fù)雜度下降為n（目前只能在這個題目中得到證明算法正確性）

---

半小時之后我又回來了。。因為還是對卡常的事耿耿于懷，于是就去把迪杰斯特拉+優(yōu)先隊列的那個代碼，把vector開的鄰接表改成了數(shù)組模擬鏈表的鄰接表了，交了一發(fā)，A了。這是遇到的第二個卡vector鄰接表的題目了。。有點坑的還是，那個代碼也掛上來吧，對比一下：?

迪杰斯特拉+雙端隊列：（545ms）

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<deque> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=510;int head[N][N];int cnt;struct edge {int x,y;int dis;int next; }edge[N*N*10];void addedge(int x,int y,int xx,int yy,int dis) {edge[cnt].x=xx;edge[cnt].y=yy;edge[cnt].dis=dis;edge[cnt].next=head[x][y];head[x][y]=cnt++;edge[cnt].x=x;edge[cnt].y=y;edge[cnt].dis=dis;edge[cnt].next=head[xx][yy];head[xx][yy]=cnt++; }int n,m;char maze[N][N];struct Node {int x,y,dis;Node(int X,int Y,int DIS){x=X;y=Y;dis=DIS;} };int d[N][N];bool vis[N][N];void Dijkstra() {d[0][0]=0;deque<Node>q;q.push_back(Node(0,0,0));while(!q.empty()){Node cur=q.front();q.pop_front();int x=cur.x;int y=cur.y;if(vis[x][y])continue;vis[x][y]=true;for(int i=head[x][y];i!=-1;i=edge[i].next){int xx=edge[i].x;int yy=edge[i].y;int w=edge[i].dis;if(!vis[xx][yy]&&d[xx][yy]>d[x][y]+w){d[xx][yy]=d[x][y]+w;if(w)q.push_back(Node(xx,yy,d[xx][yy]));elseq.push_front(Node(xx,yy,d[xx][yy]));}}} }int main() {int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s",maze[i]);cnt=0;for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){head[i][j]=-1;vis[i][j]=false;d[i][j]=inf;}for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(maze[i][j]=='/'){addedge(i,j,i+1,j+1,1);addedge(i,j+1,i+1,j,0);}else{addedge(i,j,i+1,j+1,0);addedge(i,j+1,i+1,j,1);}}Dijkstra();if(d[n][m]==inf)printf("NO SOLUTION\n");elseprintf("%d\n",d[n][m]);}return 0; }

迪杰斯特拉+優(yōu)先隊列：（2662ms）

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=510;int head[N][N];int cnt;struct edge {int x,y;int dis;int next; }edge[N*N*10];void addedge(int x,int y,int xx,int yy,int dis) {edge[cnt].x=xx;edge[cnt].y=yy;edge[cnt].dis=dis;edge[cnt].next=head[x][y];head[x][y]=cnt++;edge[cnt].x=x;edge[cnt].y=y;edge[cnt].dis=dis;edge[cnt].next=head[xx][yy];head[xx][yy]=cnt++; }int n,m;char maze[N][N];struct Node {int x,y,dis;Node(int X,int Y,int DIS){x=X;y=Y;dis=DIS;}bool operator<(const Node& a)const{return dis>a.dis;} };vector<Node>node[N][N];int d[N][N];bool vis[N][N];void Dijkstra() {d[0][0]=0;priority_queue<Node>q;q.push(Node(0,0,0));while(!q.empty()){Node cur=q.top();q.pop();int x=cur.x;int y=cur.y;if(vis[x][y])continue;vis[x][y]=true;for(int i=head[x][y];i!=-1;i=edge[i].next){int xx=edge[i].x;int yy=edge[i].y;int w=edge[i].dis;if(!vis[xx][yy]&&d[xx][yy]>d[x][y]+w){d[xx][yy]=d[x][y]+w;q.push(Node(xx,yy,d[xx][yy]));}}} }int main() {int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s",maze[i]);cnt=0;for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){head[i][j]=-1;vis[i][j]=false;d[i][j]=inf;}for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(maze[i][j]=='/'){addedge(i,j,i+1,j+1,1);addedge(i,j+1,i+1,j,0);}else{addedge(i,j,i+1,j+1,0);addedge(i,j+1,i+1,j,1);}}Dijkstra();if(d[n][m]==inf)printf("NO SOLUTION\n");elseprintf("%d\n",d[n][m]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的AcWing - 175 电路维修(思维建边+最短路)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。