★☆   输入文件：city.in   输出文件：city.out   简单对比

时间限制：1 s   内存限制：128 MB

问题描述

有 n 个 城市，它们之间的交通情况已知。现在要求根据一个出发点Cs和一个到达点Cd，请编程序，由计算机找到从城市Cs 到 Cd 的一条路径，要求经过城市最少。

【输入格式】

输入文件： city.in

输入由若干行组成，第一行有四个整数，n（1≤n≤50）、m（1≤m≤n*n）和s（1≤s≤n）、e（1≤e≤n）；n表示城市数，m表示道路数，s和e表示出发点和到达点。

第 2至m+1行是m 条边的 信息，每行两个整数，为边的起点和终点。

【输出格式】

输出文件： city.out

一个整数,经过城市的个数（包括起点和终点）

【输入样例】

输入文件名：city.in

6 6 1 5 

1 3 

2 6 

3 6 

3 2 

6 4 

4 5

输出文件名：city.out

5

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=55;const int INF=99999999;int map[N][N];int n,m,start,endd;int u,v;inline int read(){	int x=0;int f=1;char c=getchar();	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();	return x*f;}int main(){	freopen("city.in","r",stdin);	freopen("city.out","w",stdout);	n=read(),m=read(),start=read(),endd=read();	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)			map[i][j]=INF;	for(int i=1;i<=n;i++)		map[i][i]=0;	for(int i=1;i<=m;i++)		u=read(),		v=read(),		map[u][v]=map[v][u]=1;	for(int k=1;k<=n;k++)		for(int i=1;i<=n;i++)			for(int j=1;j<=n;j++)				map[i][j]=min(map[i][j],map[i][k]+map[k][j]);	printf("%d",map[start][endd]+1);	return 0;}