时间限制: 1 s 空间限制: 256000 KB 题目等级 : 青铜 Bronze

题目描述 

Description

HYY要娶山那头的JCH，可毕竟是山路，十分崎岖，他又十分的单（bai）纯（chi），为了帮他娶到JCH，他请聪明的你帮他。

 

HYY到JCH之间有n个地点（包括起点（1）和终点（n）），m条路，每个地点之间可能有路连接，也可能没有。

每个地点有一个黑心商家，只要你来了这，就要给过路费（什么鬼故事~~）。

设每个地点的过路费相同。给你n和m，以及每条路的两段的地点，请你求出HYY最少要经过几个地点，让他花最少的钱到达JCH的家（毕竟迎亲花了HYY很多钱嘛）。（此题我在洛谷上发了比赛）

输入描述 

Input Description

第一行为两个整数，n和m

以下2到m+1行，为一条路连接的两个地点（无向）

输出描述 

Output Description

一个整数，求出HYY最少经过几个地点（包括起点和终点）

如果没有通路，输出-1

样例输入 

Sample Input

4 3

1 2

2 3

2 4

样例输出 

Sample Output

3

（1-2-4）

数据范围及提示 

Data Size & Hint

n<=200,m<=n*n

in文件随机：

 

var n,k,i,x,y:longint; f:array[1..200,1..200]of longint;begin readln(n,k); writeln(n,' ',k); randomize; for i:=1 to k do  begin   repeat    x:=random(n)+1;    if i=1 then x:=1;    y:=random(n)+1;    if i=k then y:=n;    if (x<>n)and(x
      
       <>n)and(x
      

floyd记录路径 丫的我竟然打了近一小时 QAQ

学习自这位（点击传送）

#include
       
        #include
        
         using namespace std;int N;int map[201][201],b[201],path[201][201];void init(){    int i,j;    for(i=1;i<=N;i++)    {        for(j=1;j<=N;j++)        {            map[i][j]=9999999;            path[i][j]=j;        }    }}void floyd(){    int i,j,k;    for(k=1;k<=N;k++)    {        for(i=1;i<=N;i++)        {            for(j=1;j<=N;j++)            {                if(map[i][j]>map[i][k]+map[k][j])                {                    map[i][j]=map[i][k]+map[k][j];                    path[i][j]=path[i][k];                }               }        }    }}int main(){    int m,len;    cin>>N>>m;        init();        while(m--)    {                    int a,b;             scanf("%d%d",&a,&b);            map[a][b]=map[b][a]=1;        }        floyd();        if(map[1][N]>=9999999)        {            cout<<"-1";            return 0;        }        int u=1,v=N;        int tmp=u,ans=1;        while(tmp!=v)        {            ans++;            tmp=path[tmp][v];        }        cout<