佛山微网站开发哪家好,吕梁网站建设,做设计比较好的网站,网站建设中色无极给定一个 n 个点 m 条边的有向图#xff0c;图中可能存在重边和自环。
所有边的长度都是 1#xff0c;点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离#xff0c;如果从 1 号点无法走到 n 号点#xff0c;输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接…给定一个 n 个点 m 条边的有向图图中可能存在重边和自环。
所有边的长度都是 1点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离如果从 1 号点无法走到 n 号点输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行每行包含两个整数 a 和 b表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
数据范围
1≤n,m≤10^5
输入样例
4 5
1 2
2 3
3 4
1 3
1 4输出样例
1
思路
这道题因为所有边的长度都是 1即每条边权重都是1所以可以用BFS找最短路和之前写的找迷宫出口一样。走迷宫BFS宽度优先搜索-CSDN博客 注意
int d[N]; //存距离
memset(d,-1,sizeof(d)); //距离初始化
这里我们把存距离的数组全部初始化为-1就可以实现如果从 1 号点无法走到 n 号点输出 −1。
这里是用邻接表来存储这些有向图的和之前的哈希表拉链法很像。模拟散列表哈希表拉链法-CSDN博客 void add(int a,int b) //增加一条a到b节点的边
{e[idx]b;ne[idx]h[a];h[a]idx;idx;
}
这就是增加一条从a到b的边的代码
示例代码
#includeiostream
#includecstring
#includequeueusing namespace std;const int N1e510;int h[N],e[N],ne[N],idx; //ne存的是下标
int d[N]; //存距离
int n,m;void add(int a,int b) //增加一条a到b的边
{e[idx]b;ne[idx]h[a];h[a]idx;idx;
}int bfs()
{memset(d,-1,sizeof(d)); //距离初始化queueint q; //创建队列d[1]0; //起点是1号点q.push(1); //起点入队while(q.size()) //队列不为空时{int tq.front(); //取出队头q.pop();for(int ih[t];i!-1;ine[i]) //拓展队头的点//h[t]是t指向的头结点下标,ih[t],那么ne[i]就是头结点的下一个坐标{int je[i];if(d[j]-1) //如果拓展的点没被搜过就拓展{d[j]d[t]1;q.push(j); //拓展点入队}}}return d[n]; //返回n号点到1号点距离
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnm;memset(h,-1,sizeof(h));while(m--){int a,b;cinab;add(a,b);}coutbfs()endl;return 0;
}
