Time Limit: 1 second
Memory Limit: 128 MB

【問題描述】

　 在一個神奇的小鎮上有著一個特別的電車網絡，它由一些路口和軌道組成，每個路口都連接著若干個軌道，每個軌道都通向一個路口（不排除有的觀光軌道轉一圈后返回路口的可能）。在每個路口，都有一個開關決定著出去的軌道，每個開關都有一個默認的狀態，每輛電車行駛到路口之后，只能從開關所指向的軌道出去，如果電車司機想走另一個軌道，他就必須下車切換開關的狀態。 為了行駛向目標地點，電車司機不得不經常下車來切換開關，于是，他們想請你寫一個程序，計算一輛從路口A到路口B最少需要下車切換幾次開關。

【輸入格式】

第一行有3個整數2<=N<=100，1<=A，B<=N，分別表示路口的數量，和電車的起點，終點。 接下來有N行，每行的開頭有一個數字Ki(0<=Ki<=N-1)，表示這個路口與Ki條軌道相連，接下來有Ki個數字表示每條軌道所通向的路口，開關默認指向第一個數字表示的軌道。

【輸出格式】

輸出文件只有一個數字，表示從A到B所需的最少的切換開關次數，若無法從A前往B，輸出-1。

【數據規模】

Sample Input1

3 2 1 2 2 3 2 3 1 2 1 2

Sample Output1

0

【題解】

這里的切換一次開關。可以看做是一條邊的權值。然后就能把這個問題轉化為最短路問題了。從起點開始進行spfa。然后枚舉出度的時候。除了第一個出度權值為0之外。其他的邊的權值都為1.(可以這樣做是因為。可以肯定從某個節點出去之后是不會再回來的。因為那樣不可能讓答案更優)

dis[s] = 0,其他dis值為-1.方便輸出。然后-1就相當于正無窮。在更新的時候特判一下即可。

最后輸出dis[t];

【代碼】

#include <cstdio> #include <cstring>int n, a[101][101] = { 0 },s,t,dis[101],dl[10000];int main() {scanf("%d%d%d", &n,&s,&t);for (int i = 1; i <= n; i++){scanf("%d", &a[i][0]);//輸入第i個點的出度for (int j = 1; j <= a[i][0]; j++)//依次輸入出度信息。scanf("%d", &a[i][j]);}memset(dis, 255, sizeof(dis));//dis數組初始化為正無窮(-1)bool exsit[101] = { 0 };//一開始所有的點都不存在于隊列中。dis[s] = 0;//起點不需要切換開關。int head = 0, tail = 1;exsit[s] = true;//一開始把起點加入到隊列中去。dl[1] = s;//把起點放在第一個位置。while (head != tail){head++;exsit[dl[head]] = false;//取出頭結點。標記其已經不在隊列中了。int x = dl[head];for (int i = 1; i <= a[x][0]; i++){int w = i == 1 ? 0 : 1;//如果是第一個出度則花費為0否則為1int y = a[x][i];if (dis[y] == -1 || dis[y] > dis[x] + w)//如果為正無窮或者要更新答案{dis[y] = dis[x] + w;//則更新答案。if (!exsit[y])//如果隊列中不存在y結點。則把y結點加入到隊列中去。{exsit[y] = true;tail++;dl[tail] = y;}}}}printf("%d\n", dis[t]);//最后輸出到終點的最短距離。return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7632291.html

總結

以上是生活随笔為你收集整理的【u018】电车的全部內容，希望文章能夠幫你解決所遇到的問題。

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