題目鏈接：點擊查看

題目大意：火車從起點開到終點，軌道上有很多岔路口，每個岔路口都有很多方向（火車能夠選擇任意一個方向行駛），但是默認

的是第一個方向，如果要選擇其他的方向需要增加一次切換的操作，問最少需要切換幾次可以從起點到達終點。

題目分析：這個題雖然題意有點難理解，但說實話我第一次讀完題意后就能夠理解題意了，但是卻毫無思路，陷入了思維定勢中。

因為這個題是在最短路專題中出現的，所以會下意識的往最短路上靠，不過最后還是看了別人的題解才豁然開朗，原來是個水題。

看來不能只做板子題，還是得多做點變形的題，加深對算法的理解才行啊！

大水題，n也比較小，偷個懶直接用的floyd暴力點做出來了，記得別忘了輸出-1的情況，直接上代碼了：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int maze[N][N];int main() { // freopen("input.txt","r",stdin);int n,st,ed;while(scanf("%d%d%d",&n,&st,&ed)!=EOF){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)maze[i][j]=i==j?0:inf;for(int i=1;i<=n;i++){int k;scanf("%d",&k);for(int j=1;j<=k;j++){int p;scanf("%d",&p);if(j==1){maze[i][p]=0;}else{maze[i][p]=1;}}}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++){if(maze[i][k]==inf)continue;for(int j=1;j<=n;j++)maze[i][j]=min(maze[i][j],maze[i][k]+maze[k][j]);}if(maze[st][ed]==inf)cout<<-1<<endl;elsecout<<maze[st][ed]<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 1847 Tram(最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

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