学步园

H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。    一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路已士 可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。    现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1…S公园巴士站的编号为N。   
写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程 中换车的次数最少。

输入

测试数据有多组.每组数据的第一行有两个数字M和N(1<=M<=100 1<N<=500），表示开通了M条单程巴士线路，总共有N个车站。 从第二行到第M+1行依次给出了第1条到第M条巴士线路的信息。 其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。 当M=N=0是结束.

输出

输出数据只有一行。 如果无法乘巴士从饭店到达S公园，则输出"N0"，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到达•

样例输入

3 7
6 7
4 7 3 6
2 1 3 5

样例输出

2

此题显然是图论中的算法，考虑采用迪杰斯特拉算法

#include <stdio.h>
#define MAX 20000000
int a[501][501];
int s[501], dist[501];

int main()
{
	while(1)
	{
		int m, n;
		int i, j, k;
		int temp,u;
		scanf("%d %d\n", &m, &n);
		if(m == 0 && n == 0) break;
		for(i = 1; i <= n; i ++)
			for(j = 1; j <= n; j ++)
				a[i][j] = MAX;
		for(i = 0; i < m; i ++)
		{
			k = 0;
			while(1)
			{
				char ch;
				scanf("%d%c", &s[k ++], &ch);
				for(j = 0; j < k; j ++)
					a[s[j]][s[k-1]] = 0;
				if(ch == '\n') break;
			}
		}
		for(i = 1; i <= n; i++)   
		{   
			dist[i] = a[1][i];   
			s[i] = 0;   
		}   
		dist[1] = 0;   
		s[1] = 1;
		for(i = 1; i <= n; i ++)   
		{   
			temp = MAX;
			u = 1;  
			for(j = 1; j <= n;j ++)   
				if(!s[j]&&(dist[j] <temp))   
				{   
					u = j;   
					temp  = dist[j];  
				}
				s[u] = 1;
				for(j = 1; j <= n; j ++)   
					if(!s[j] && (a[u][j] < MAX)) 
					{
						int  newdist = dist[u]+a[u][j]+1;
						if(newdist < dist[j])
							dist[j] = newdist;
					}
		}
		if(dist[n] != MAX)
		{
			printf("%d\n", dist[n]);
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}