题意:求1点到2点的所有能够到2点的所有通路里的的最大路径(这里的路径特指两点之间的线段)的最小值。
这题对我来说收获颇丰,我们可以修改dijkstra里面的松弛函数,使得其变为求每个点的满足条件的值,并用dist数组来记录。详见代码。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define INF 0x3f3f3f3f #define INF2 -0x3f3f3f3f typedef struct Node { double x; double y; }; Node nodes[205*2]; typedef struct Egde { int l; int r; double value; }; double a[205*2][205*2]; double dist[205*2]; bool visited[205*2]; int n,sx,sy,ex,ey; double Max; void dijkstra() { visited[1]=true; for(int i=1; i<=n; i++) { dist[i]=a[1][i]; } for(int i=1; i<=n; i++) { int Min=INF,node=0; for(int j=1; j<=n; j++) { if(!visited[j]&&Min>dist[j]) { Min=dist[j]; node=j; } } if(node==0) return; visited[node]=true; for(int j=1; j<=n; j++) { Max=max(dist[node],a[node][j]);//构成dist[node]和a[node][j]里找最大的边,因为这两条边来构成一条新的dist[j] //用为要去最大边里的最小边,那么我们就要把它和原来的dist[j]进行比较 //再把较小的边赋给dist[j]来成为新的dist[j]以便进行下次更新 dist[j]=min(dist[j],Max); dist[j]=min(dist[j],Max); } } } int main() { int sym=0; while(scanf("%d",&n)&&n!=0) { sym++; memset(nodes,0,sizeof(nodes)); memset(a,0x3f,sizeof(a)); memset(dist,0x3f,sizeof(dist)); memset(visited,false,sizeof(visited)); for(int i=1; i<=n; i++) { scanf("%lf%lf",&nodes[i].x,&nodes[i].y); } for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { double d=sqrt((nodes[i].x-nodes[j].x)*(nodes[i].x-nodes[j].x)+(nodes[i].y-nodes[j].y)*(nodes[i].y-nodes[j].y)); a[i][j]=a[j][i]=d; a[i][i]=0; } } Max=INF; dijkstra(); printf("Scenario #%d\n",sym); printf("Frog Distance = %.3f\n\n",dist[2]); } return 0; }
相关推荐
标题中的"POJ2253-Frogger【Floyd】"是指北京大学在线编程平台POJ(Problem Set)上的第2253题——“Frogger”,这是一道编程题目,通常涉及到算法和逻辑思维。Floyd在这里指的是弗洛伊德算法,它可能在这道题的解决...
dijkstra 算法 需要考虑重边.........
【标题】"POJ1062-Expensive dowry【dijkstra】"涉及的问题是图论中的一个重要算法——Dijkstra算法,这是一个用于求解单源最短路径问题的算法,通常在计算机科学和信息技术领域有广泛应用,如路由选择、网络优化等...
* 最短路径算法:例如 Dijkstra、Bellman-Ford、Floyd、Heap+Dijkstra,例如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
- 最短路径算法:如Dijkstra算法和Bellman-Ford算法,用于找到两点间的最短路径,如`poj1062, poj2253`。 - 最小生成树算法:如Prim算法和Kruskal算法,用于找出图中的最小生成树,如`poj1789, poj2485`。 - 拓扑...
POJ2009年最新版,相当详细.................
- **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...
- (poj1860, poj3259, poj1062, poj2253, poj1125, poj2240):介绍迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)、弗洛伊德算法(Floyd)等。 - 使用堆优化的迪杰斯特拉算法。 3. **最小生成树...
解题者可能使用了栈来存储运算符和操作数,逐步处理逻辑表达式,或者采用了类似Dijkstra的短路评估法来简化表达式并判断其真伪。 在解题报告中,可能会详细解释如何将逻辑表达式转换为后缀表达式,如何利用栈来执行...
Dijkstra算法、Bellman-Ford算法和Floyd算法分别适用于无负权边、有负权边和所有类型的加权图,而Heap-Dijkstra结合了Dijkstra算法与堆优化,提高了解决大规模图问题的效率。 #### 最小生成树 Prim算法和Kruskal...
- **最短路径算法**:包括dijkstra、bellman-ford、floyd和heap+dijkstra,如poj1860等,用于找到节点间的最短距离。 - **最小生成树算法**:prim和kruskal算法,如poj1789,用于找到图的最小成本连接。 - **拓扑...
- POJ 1062、POJ 2253:涉及Bellman-Ford算法的应用场景。 - POJ 1125、POJ 2240:Floyd算法的典型实例。 ##### 最小生成树 - **算法**: - Prim算法 - Kruskal算法 - **题目示例**: - POJ 1789、POJ 2485:...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...
从给定的文件信息来看,这是一份关于POJ(Pat Online Judge)平台上的编程题目的分类汇总。POJ是北京大学设立的一个在线编程评测系统,提供了大量的编程题目供学习者练习,涵盖了各种算法和数据结构知识。下面将对这...
#### 2267 *From Dusk till Dawn or: Vladimir the Vampire - 最短路 - **知识点**:最短路径算法。 #### 2289 Jamie's Contact Groups - 网络流 - **知识点**:网络流算法。 #### 2337 Catenyms - 欧拉通路 - ...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...