1175: 货运费用 (不带权值的最短路径+bfs)

本文主要是介绍1175: 货运费用 (不带权值的最短路径+bfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1175: 货运费用

菜鸟生成记(17)

又双叒叕是最短路径的水题;不过没必要用Dijkdtra算法,因为这一题的边权仅作为该边是否可通过的判断条件;

那么就可以把这个图想象成一个迷宫(二维矩阵迷宫),迷宫最短路径一个bfs就可以解决;

struct st{int v;//顶点int s;//到达该顶点的步数st(){s=0;//队列元素步数置0}
}q[M];//队列

AC代码

#include<bits/stdc++.h>
using namespace std;
const int M=1e+3+10,inf=1e+5+10;
struct st{int v;int s;st(){s=0;}
}q[M];
int a[M][M];
int book[M]={0};
int n,m,w;
void init()
{for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)a[i][j]=-inf;//负无穷表示该边不通
}
void bfs(int u,int v)
{int f=0,r=0,flag=0;q[r++].v=u;book[u]=1;while(f!=r){int k=q[f].v;for(int i=1;i<=n;i++){if(book[i]==0&&a[k][i]>=w){book[i]=1;q[r].s=q[f].s+1;//儿子继承父亲的步数+1q[r++].v=i;if(i==v)//到达终点结束{flag=1;break;}}}if(flag==1)//这也要加个结束,不然后续的顶点会继续入队,队尾存放的就不是终点值了break;f++;//队头指针一定要最后移动}if(flag==1)//可到终点cout<<q[r-1].s<<endl;//输出到达终点的最短步数elsecout<<-1<<endl;//不能到达终点
}
int main()
{cin>>n>>m>>w;init();for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;a[x][y]=z;a[y][x]=z;} bfs(1,n);return 0;
}