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<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
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;
}
原文：http://www.cnblogs.com/lyqlyq/p/7158611.html