感慨

周五比賽的測試題，結果到比賽結束也沒有讀懂題意。。。給的樣例太少了，我一直以為我是不是spfa敲錯了。。。沒想到中間還有卡的地方

分析

題目中的一句耐人尋味的話“路徑上的所有點的出邊所指向的點都直接或間接與終點連通。”就是這句話直接忽略掉了spfa才導致的WA。這句話的意思實際上是說如果這條路徑上所有連通的點只要有一個點沒有與終點連通，那么這條路就不合適。換句話說就是比如1-2-3-4是以1為起點4為終點的一條路，我們現在找到的一條。然后如果3-5-6意思是3和5和6又相連，其中如果5和6有一個點所連通的點里面沒有到達終點的，那么3這個點就不合適了。我們假設只能由5-6,6沒有除了5之外連通的點了，那么3這個點就是不合適的。就算這是你找到的最短路，那也是不合適的。還需要再找到比最短路長的合適的路

洛谷第二個樣例的圖（咱們比賽應該把樣例2出上啊，要不看不懂題啊。。。也可能是我語文不好。。。）

其中紅線是答案的路線

解法

①反向存邊

第一遍我們要找到所有與終點連通的邊，所以我們應該從終點開始bfs整個圖，然后去尋找與終點連通的邊，這里我們需要反向存邊

②枚舉各個頂點

這一步是為了確保上述分析中3這樣的點的存在，把他們找出來。注意這個地方要開其他的臨時的數組，避免尋找的時候出現混亂

③SPFA

直接把所有能符合規定的點入隊spfa即可

④輸出dis數組

這里注意判斷條件，如果不連通直接-1

具體看下面的代碼，代碼里面也有注釋

#include <bits/stdc++.h> using namespace std; //我這里用的是vector存邊所以先開一個結構體 struct node {int to,cost; }; //map是為了能夠避免迷之re，然后long long是為了避免spfa int爆表成負數 map<long long,long long> vis,bk,bk1,dis,bk2; //兩個隊列， q是spfa qq是bfs queue<int> q,qq; //兩個存邊的vector vector <node> G1[10005]; vector <node> G2[10005]; const int inf=INT_MAX; int main() {ios::sync_with_stdio(0);//關閉同步三步走，只要c++就要關同步cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;//輸入點和邊的個數while(m--){int t1,t2;cin>>t1>>t2;G1[t2].push_back((node){t1,1});//反向存邊G2[t1].push_back((node){t2,1});//正向存邊}int s,e;cin>>s>>e;//輸入s起點和e終點for(int i=1;i<=n;i++)//初始化dis數組，為了spfadis[i]=i==s?0:inf;qq.push(e);//從e開始bfsbk2[e]=1;//bk2數組是給bfs剪枝用的while(qq.size()){int f=qq.front();qq.pop();bk[f]=1;vis[f]=1;for(int i=0;i<G1[f].size();i++)//直接進行所有的遍歷，如果滿足條件那么就標記上{vis[G1[f][i].to]=1;//1號標記bk[G1[f][i].to]=1;//2號標記if(!bk2[G1[f][i].to])//剪枝，避免已經入隊過的點重新入隊{bk2[G1[f][i].to]=1;qq.push(G1[f][i].to);}}}for(int i=1;i<=n;i++)//枚舉各個點{if(!vis[i])//如果他與終點不連通for(int j=0;j<G1[i].size();j++)if(vis[G1[i][j].to])//如果他的連通的點與終點連通bk[G1[i][j].to]=0;//去掉標記}q.push(s);//spfa起點入隊while(q.size()){int p=q.front();q.pop();bk1[p]=0;if(bk[p])//如果是一個標記的點{for(int i=0;i<G2[p].size();i++)//老生常談的spfa模板{if(dis[G2[p][i].to]>dis[p]+G2[p][i].cost){dis[G2[p][i].to]=dis[p]+G2[p][i].cost;if(!bk1[G2[p][i].to]){bk1[G2[p][i].to]=1;q.push(G2[p][i].to);}}}}}if(dis[e]<INT_MAX)//判斷一下條件輸出dis數組即可cout<<dis[e];elsecout<<-1; }

轉載于:https://www.cnblogs.com/baccano-acmer/p/9979042.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的洛谷 P2296 寻找道路的全部內容，希望文章能夠幫你解決所遇到的問題。

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