Tram
TimeLimit:1000MS MemoryLimit:30000K
64-bit integer IO format:%lld
Problem Description
Tram network in Zagreb consists of a number of intersections and rails connecting some of them. In every intersection there is a switch pointing to the one of the rails going out of the intersection. When the tram enters the intersection it can leave only in the direction the switch is pointing. If the driver wants to go some other way, he/she has to manually change the switch. When a driver has do drive from intersection A to the intersection B he/she tries to choose the route that will minimize the number of times he/she will have to change the switches manually. Write a program that will calculate the minimal number of switch changes necessary to travel from intersection A to intersection B.
Input
The first line of the input contains integers N, A and B, separated by a single blank character, 2 <= N <= 100, 1 <= A, B <= N, N is the number of intersections in the network, and intersections are numbered from 1 to N. Each of the following N lines contain a sequence of integers separated by a single blank character. First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection. Next Ki numbers represents the intersections directly connected to the i-th intersection.Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.
Output
The first and only line of the output should contain the target minimal number. If there is no route from A to B the line should contain the integer "-1".
SampleInput
3 2 1 2 2 3 2 3 1 2 1 2
SampleOutput
0
看了最短路Dijkstra算法差不多最全最详细的博客：https://www.cnblogs.com/jason2003/p/7222182.html
差不多就是贪心算法，定义一个二维数组map，开始先将有路的起始点都赋值，然后没路的都取值为0x3f3f3f3f3f（用了这么久还不懂这个是什么）,
然后从最源点开始搜索，查找到最源点的的最短路，将这个点记录下来，这个点到源点的最短路就已经确定了，因为已经可以直接通过的，然后将记录
的这个点在作为源点，然后遍历到各个点，记得每次被当作源点的点都要标记下来，不能再找回去，要是现在的源点到未标记的各个点+源点到最初源点<
这个点直接到最初源点的值，就可以将这个点到最初源点的值变为较小的那个，遍历过去现在这个源点连的点，最终又可以找到此点到最初源点的最短路
径，就是这样一个个遍历过去就可以找到各个点到最初源点的最短路径。
附上代码：
1 /** 2 rid: 390382 3 user: 965251545 4 time: 2020-04-08 21:08:27 5 result: Accepted 6 */ 7 #include <stdio.h> 8 #define INF 0x3f3f3f3f 9 int map[105][105],dis[10005],vis[10005]; 10 int n,a,b; 11 void init() 12 { 13 for(int i=1;i<=n;i++) 14 { 15 for(int j=1;j<=n;j++) 16 { 17 if(i==j) 18 map[i][j]=0; 19 else 20 map[i][j]=INF; 21 } 22 } 23 } 24 void Dijkstra() 25 { 26 for(int i=1;i<=n;i++) 27 dis[i]=map[a][i];//记录每个点到源点的距离 28 vis[a]=1;//从源点开始搜索 29 for(int i=1;i<=n;i++) 30 { 31 int w=-1,min=INF; 32 for(int j=1;j<=n;j++)//找到到源点的最短距离 33 { 34 if(!vis[j]&&dis[j]<min)//有到源点的路 35 { 36 w=j; 37 min=dis[j]; 38 } 39 } 40 if(w==-1||w==b)//没有到源点的点，或者已经找到末点 41 break; 42 vis[w]=1;//记录下最短路的点 43 for(int j=1;j<=n;j++) 44 { 45 if(!vis[j]&&dis[j]>dis[w]+map[w][j])//直接到源点的路大于转弯的就进行改变 46 dis[j]=dis[w]+map[w][j]; 47 } 48 } 49 } 50 int main(void) 51 { 52 int num,w; 53 scanf("%d%d%d",&n,&a,&b); 54 init(); 55 for(int i=1;i<=n;i++) 56 { 57 scanf("%d",&num); 58 for(int j=0;j<num;j++) 59 { 60 scanf("%d",&w); 61 if(j==0) 62 map[i][w]=0;//直接可以到路径为0 63 else 64 map[i][w]=1; 65 } 66 } 67 Dijkstra(); 68 if(dis[b]>=INF)//没有可以到b的路 69 printf("-1 "); 70 else 71 printf("%d ",dis[b]); 72 }
——————————————————————————————————————————————————————————————————————————————————————————————————
"I don't want to be the next Michael Jordan,I only want to be Kobe Bryant."
———Kobe Bryant
