宽度优先搜索之城市最短路问题

ゝ一纸荒年。 2022-07-12 12:44 178阅读 0赞

**题目描述：**

**有 n 个 城市，它们之间的交通情况已知。现在要求根据一个出发点Cs和一个到达点Cd，请编程序，由计算机找到从城市Cs 到 Cd 的一条路径，要求经过城市最少。  
【输入格式】  
输入由若干行组成，第一行有四个整数，n（1≤n≤50）、m（1≤m≤n\*n）和s（1≤s≤n）、e（1≤e≤n）；n表示城市数，m表示道路数，s和e表示出发点和到达点。  
第 2至m+1行是m 条边的 信息，每行两个整数，为边的起点和终点。  
【输出格式】  
一个整数,经过城市的个数（包括起点和终点）**

#include <iostream>
    #include <queue>
    using namespace std;
    int G[100][100];
    bool M[100];
    int D[100];
    int main()
    {
    
    	int n;
    	cin>>n;
    
    	int m;
    	cin>>m;
    
    	int s,e;
    	cin>>s>>e;
    
    	
    
    
    
    	for(int i=1;i<=n;i++)
    	{
    		M[i]=true;
    	}
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    			G[i][j]=-1;
    
    	for(int i=1;i<=m;i++)
    	{
    		int a,b;
    		cin>>a>>b;
    		G[a][b]=1;
    	}
    
    	D[s]=1;
    	M[s]=false;
    	queue<int> Q;
    	Q.push(s);
    
    	while(!Q.empty())
    	{
    		int u=Q.front();
    		Q.pop();
    
    		for(int v=1;v<=n;v++)
    		{
    			if(M[v]&&G[u][v]>0)
    			{
    				Q.push(v);
    				M[v]=false;
    				D[v]=D[u]+1;
    			}
    		}
    	}
    	cout<<D[e];
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，178人围观）

还没有评论，来说两句吧...

相关阅读

相关宽度优先搜索算法（BFS）

先从左向右，再从右向左地对每一层节点进行遍历以示例1为例：即。

旧城等待，/ 2024年04月25日 08:45/ 0 赞/ 91 阅读

相关宽度优先搜索算法-BreadthFirstSearch(BFS)

package com.xch3.wide; import java.util.ArrayList; import java.util.Lis

左手的ㄟ右手/ 2024年04月06日 10:26/ 0 赞/ 95 阅读

相关最短路问题

文章目录最短路问题一.朴素dijkstra算法二.堆优化版dijkstra 算法三.Bellman-Ford算法

逃离我推掉我的手/ 2023年10月04日 11:57/ 0 赞/ 55 阅读

相关宽度优先搜索遍历算法-8.4迷宫问题

例8.4迷宫问题如图所示，给出一个nm的迷宫图和一个入口、一个出口编写一个程序，打印从一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-

怼烎@/ 2023年07月06日 13:19/ 0 赞/ 5 阅读

相关广度优先搜索 / 宽度优先搜索 (Breadth First Search，BFS) - 层层递进

广度优先搜索 / 宽度优先搜索 (Breadth First Search，BFS) - 层层递进深度优先搜索方法可用于解决从迷宫起点开始寻找一条通往迷宫中目标位置最

小鱼儿/ 2023年02月10日 12:28/ 0 赞/ 17 阅读

相关 Poj 1724 ROADS (搜索最短路 BFS优先队列)

题意：有n 城市，r条路，有k这么多的钱。每条路都有长度和花费两个参数，求从1到n最短且总花费不超过k的长度。思路：优先队列。每次将长度最小的出队，然后判断花费，位超限就将

短命女/ 2023年01月06日 11:55/ 0 赞/ 148 阅读

相关宽度优先搜索之城市最短路问题

题目描述：有 n 个城市，它们之间的交通情况已知。现在要求根据一个出发点Cs和一个到达点Cd，请编程序，由计算机找到从城市Cs 到 Cd 的一条路径，要求经过城市最少。

ゝ一纸荒年。/ 2022年07月12日 12:44/ 0 赞/ 179 阅读

相关宽度优先搜索

题目链接：http://192.168.167.168/JudgeOnline/problem.php?cid=1010&pid=0 解题思路：n来标记节点，方便记

た入场券/ 2022年07月10日 04:22/ 0 赞/ 182 阅读

相关广度/宽度优先搜索(BFS)

本文转自[http://rapheal.iteye.com/blog/1526861][http_rapheal.iteye.com_blog_1526861] 适合初学

超、凢脫俗/ 2022年06月17日 01:29/ 0 赞/ 283 阅读

相关最短路问题

最短路问题有4种算法+广搜分为单源最短路和多源最短路 floyd算法多源最短路 O(n^3) Dijkstra 单源最短路 O ford算法

骑猪看日落/ 2021年10月30日 02:48/ 0 赞/ 351 阅读