Input
Output
Sample Input
3 2 1 2 2 3 2 3 1 2 1 2
Sample Outpu
0
翻译：有n个点，从a到b。从一个点到另一个点之间是铁路，铁路有初始的指向，如果要改变指向，则需要搬动扳手
，问从a到b最少需要搬动几次扳手。输入第一行为n,a,b;往下n行，每行第一个数表示此点链接的轨道数，第二个数为初始轨道指向的点
，然后是其他轨道指向的点。
思路：最短路，及那个初始指向设为0，其他指向设为1，不指向的设为无穷大，然后根据最短路算法的出从a到b之间安定最小数即可。结果需要解一个判断是否有最小的答案
代码：
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15 #define mod 998244353 16 #define eps 1e-6 17 #define ll long long 18 #define INF 0x3f3f3f3f 19 using namespace std; 20 21 int n,a,b; 22 //ma表示两点之间的距离 23 int ma[105][105]; 24 //dis表示起点到其他点之间的距离 25 int dis[105]; 26 //vis表示当前点的dis是否为最短的 27 int vis[105]; 28 void dijkstra() 29 { 30 //初始化标记 31 memset(vis,0,sizeof(vis)); 32 //标记起点 33 vis[a]=1; 34 //初始化初距离 35 for(int i=1;i<=n;i++) 36 { 37 dis[i]=ma[a][i]; 38 } 39 //起点为0； 40 dis[a]=0; 41 for(int i=1;i<n;i++) 42 { 43 int mi=INF; 44 int k; 45 //找当前起点到各点之间的最短的 46 for(int j=1;j<=n;j++) 47 { 48 if(!vis[j]&&dis[j]<mi) 49 { 50 mi=dis[j]; 51 k=j; 52 } 53 } 54 //标记起点 55 vis[k]=1; 56 //更新所有的dis数据 57 for(int j=1;j<=n;j++) 58 { 59 if(dis[j]>dis[k]+ma[k][j]) 60 { 61 dis[j]=dis[k]+ma[k][j]; 62 } 63 } 64 65 } 66 } 67 int main() 68 { 69 while(~scanf("%d %d %d",&n,&a,&b)) 70 { 71 //初始化两点之间的距离 72 memset(ma,INF,sizeof(ma)); 73 for(int i=1;i<=n;i++) 74 { 75 //一样的点之间距离为0 76 ma[i][i]=0; 77 int c,d; 78 scanf("%d",&c); 79 for(int j=1;j<=c;j++) 80 { 81 scanf("%d",&d); 82 //第一个输入表示不需要变道 83 if(j==1) 84 { 85 ma[i][d]=0; 86 }//往后都需要变道 87 else 88 { 89 ma[i][d]=1; 90 } 91 } 92 } 93 dijkstra(); 94 //如果无解，则输出-1.否则输出解 95 if(dis[b]>=INF) 96 { 97 printf("-1\n"); 98 } 99 else 100 { 101 printf("%d\n",dis[b]); 102 } 103 } 104 }
Tram POJ - 1847 最短路，Dijktra算法，单向图
原文：https://www.cnblogs.com/mzchuan/p/11556175.html