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

5462 HYY迎亲I

2024-08-19 12:57:59   211人阅读

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


联系
我们