首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。