宽度优先搜索

た入场券 2022-07-10 04:22 184阅读 0赞

**题目链接：http://192.168.167.168/JudgeOnline/problem.php?cid=1010&pid=0**

**解题思路：n来标记节点，方便记录路径**

#include <iostream>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    bool M[1100];
    int Xi[1100],Yi[1100],Ri[1100];
    double D[1100];
    int P[1100];
    int n,xi,yi,ans,ansnum=0;
    void bfs()
    {
    	for(int i=1;i<=n;i++)
    		{
    			M[i]=true;
    	     }
    
    	queue<int> Q;
    	Q.push(1);
    	M[1]=false;
    	D[1]=10000;
    
    	while(!Q.empty())
    	{
    		int u=Q.front();
    		Q.pop();
    
    		for(int v=1;v<=n;v++)
    			if(M[v]&&Ri[u]+Ri[v]==sqrt(double((Xi[u]-Xi[v])*(Xi[u]-Xi[v])+(Yi[u]-Yi[v])*(Yi[u]-Yi[v]))))
    			{
    				Q.push(v);
    				D[v]=D[u]*Ri[u]/Ri[v];
    				M[v]=false;
    				P[v]=u;
    				if(Xi[v]==xi&&Yi[v]==yi)
    				{
    					ans=v;return;
    				}
    			}
    	}
    }
    int print_path(int v)
    {
    	if(v==1)
    		return 10000;
    	else
    		return print_path(P[v])+D[v];
    }
    int main()
    {
    	cin>>n>>xi>>yi;
    
    	for(int i=1;i<=n;i++)
    	{
    		cin>>Xi[i]>>Yi[i]>>Ri[i];
    	}
    	
        bfs();
    	cout<<print_path(ans);
    
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

相关 Python基于宽度优先搜索的程序综合-SyGus求解器

程序综合-SyGus求解器该项目实现了一个简单的SyGus求解器，解决了33个测试样例中的32个。该SyGus求解器自动生成测试输入、搜索可能满足条件的程序输出，再基于

清疚/ 2024年04月06日 10:21/ 0 赞/ 49 阅读

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

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

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

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

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

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

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

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

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

相关 BFS-宽度优先搜索（Breadth First Search）—1

在这篇博客[http://blog.csdn.net/hacker\_zhidian/article/details/54774013][http_blog.csdn.net_

Bertha 。/ 2022年07月11日 13:21/ 0 赞/ 190 阅读

相关宽度优先搜索

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

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

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

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

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

相关深度优先搜索与广度优先搜索

[二叉树深度优先遍历和广度优先遍历][Link 1] ![805461-20160514164458359-1600906940.png][] 　　对于一颗二叉树，深度

迈不过友情╰/ 2022年06月09日 07:57/ 0 赞/ 292 阅读