Saving James Bond HDU - 1245(多源点 floyd)

2024-04-16 02:08

本文主要是介绍Saving James Bond HDU - 1245(多源点 floyd),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape – he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
Assume that the lake is a 100×100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether he could escape.If he could,tell him the shortest length he has to jump and the min-steps he has to jump for shortest length.
Input
The input consists of several test cases. Each case starts with a line containing n <= 100, the number of crocodiles, and d > 0, the distance that James could jump. Then one line follows for each crocodile, containing the (x, y) location of the crocodile. Note that x and y are both integers, and no two crocodiles are staying at the same position.
Output
For each test case, if James can escape, output in one line the shortest length he has to jump and the min-steps he has to jump for shortest length. If it is impossible for James to escape that way, simply ouput “can’t be saved”.
Sample Input
4 10
17 0
27 0
37 0
45 0
1 10
20 30
Sample Output
42.50 5
can’t be saved

题意:
你在半径为7.5的圆上。被100*100的正方形包围。你在圆上移动,区域内有鳄鱼,你最多跳h距离,可以踩在鳄鱼上走。问最短距离,最少多少步跳出正方形。
思路:
多源点多汇点。开一个超级源点和超级汇点。算出能互相跳到的鳄鱼之间距离。然后跑最短路算法就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;
const int maxn = 105;
const double INF = 1e9;double dist(double x1,double y1,double x2,double y2)
{return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}double d[maxn][maxn],X[maxn],Y[maxn];
int step[maxn][maxn];int main()
{int n;double h;while(~scanf("%d%lf",&n,&h)){int cnt = 1;for(int i = 1;i <= n;i++){double x,y;scanf("%lf%lf",&x,&y);if(fabs(x) <= 7.5 && fabs(y) <= 7.5){continue;}X[cnt] = x, Y[cnt] = y;cnt++;}n = cnt;if(h >= 42.5){printf("42.5 1\n");continue;}for(int i = 0;i <= n;i++){for(int j = 0;j <= n;j++){d[i][j] = i == j ? 0 : INF;step[i][j] = 0;}}for(int i = 1;i < n;i++){for(int j = i + 1;j < n;j++){double tmp = dist(X[i],Y[i],X[j],Y[j]);if(tmp <= h){step[i][j] = step[j][i] = 1;d[i][j] = d[j][i] = tmp;}else{step[i][j] = step[j][i] = 0;d[i][j] = d[j][i] = INF;}}}for(int i = 1;i < n;i++){if(h + 7.5 >= dist(X[i],Y[i],0,0)){step[0][i] = step[i][0] = 1;d[0][i] = d[i][0] = dist(X[i],Y[i],0,0) - 7.5;}if(50 - X[i] <= h || X[i] + 50 <= h || 50 - Y[i] <= h || 50 + Y[i] <= h){step[i][n] = step[n][i] = 1;d[i][n] = d[n][i] = min(min(50 - X[i],X[i] + 50),min(50 - Y[i],50 + Y[i]));}}for(int k = 0;k <= n;k++){for(int i = 0;i <= n;i++){for(int j = 0;j <= n;j++){if(d[i][k] < INF && d[k][j] < INF && d[i][j] > d[i][k] + d[k][j]){d[i][j] = d[i][k] + d[k][j];step[i][j] = step[i][k] + step[k][j];}}}}if(d[0][n] == INF){printf("can't be saved\n");}else{printf("%.2f %d\n",d[0][n],step[0][n]);}}return 0;
}

这篇关于Saving James Bond HDU - 1245(多源点 floyd)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907539

相关文章

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

uva 10099(floyd变式)

题意: 有一个导游要带着一群旅客从一个城市到达另一个城市,每个城市之间有最大的旅客流量限制。 问最少几趟能将这些旅客从一个城市搞到另一个城市。 解析: 用floyd找出最小流量中的最大边,然后次数就是   ceil(总人数 / 最大承载量 - 1),-1的意思是导游每次也要在车上。 ps.老司机哭晕在厕所 代码: #include <iostream>#includ

uva 10048(floyd变式)

题意: 求两个点之间经过的路径中最大噪声最小的值。 解析: floyd的变式,每次取g[i][k] g[k][j]中的大边与当前边g[i][j]比较,取小。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#includ

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin