首页 > 代码库 > 5462 HYY迎亲I

5462 HYY迎亲I

题目描述 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

代码:

/*裸的spfa*/#include<cstdio>#include<cstring>#include<queue>#define maxn 201using namespace std;int n,m,tot,head[maxn],b[maxn];bool vis[maxn];queue<int>c;struct node{    int to,next,w;}a[maxn*maxn];void add(int x,int y,int z){    tot++;    a[tot].to=y;    a[tot].next=head[x];    a[tot].w=z;    head[x]=tot;}int spfa(){    memset(b,127/3,sizeof(b));    b[1]=0;    c.push(1);    while(c.size()!=0)    {        int i,x=c.front();        c.pop();        vis[1]=1;        for(i=head[x];i;i=a[i].next)        {            int y=a[i].to;            if(b[y]>b[x]+a[i].w)            {                b[y]=b[x]+a[i].w;                if(!vis[y])                  vis[y]=1,c.push(y);            }        }    }    if(b[n]>n)      return -2;    return b[n];}int main(){    int i,j,x,y;    scanf("%d%d",&n,&m);    for(i=1;i<=m;i++)      scanf("%d%d",&x,&y),add(x,y,1),add(y,x,1);    printf("%d",spfa()+1);//因为要输出点的个数,所以+1    return 0;}

 

5462 HYY迎亲I