題目大意：
給出一個圖，其中有一些點是出口，現在有一個罪犯有一個警察，各在兩個不同的點。其中警察有一個最大速度160，問罪犯最少需要多大的速度，保證能從某個出口逃跑。

一開始看了題目沒什么感覺，當將題目看了兩三遍后就發現只要到某一個點罪犯用的時間比警察的少則在那個點不會被抓，很顯然，到某一個點會走最短路徑。所以要用到兩次最短路算法，二分罪犯車子的速度，然后搜索在當前速度下是否可以逃脫。

注意的地方：

1、對于無解可以spfa或者bfs判斷一下，上面提出的有解的必要條件肯定沒問題

2、對于罪犯對整個圖的最短路，需要注意的是不能經過警察的起點

3、在二分速度之后，判斷可以bfs,或者dfs，便是判斷可以走到哪些點，條件就是罪犯到達的時間早于警察到達的時間，如果可以則擴展,注意的是每個點只需要判斷一次，不需要像DFS那樣恢復現場

4、這題的精度要求是1e-6,可是sample給的精度很高，搞得我們都用了1e-10，其實姿勢正確1e-6就能過，原以為樣例小數據都能這么大誤差，所以把精度控制地很嚴，導致多次TLE

PS：spfa寫錯好幾個地方 ，SB到極點

#include <iostream> #include <cstdio> #include <climits> #include <cstring> #include <queue> using namespace std; const int maxn = 110; const int inf = 1600005; int map[maxn][maxn],Exit[maxn]; int dis1[maxn],dis2[maxn],vis[maxn]; double ptime[maxn]; int n,m,e,b,p; struct node {int v,len,next; }edge[maxn*maxn]; int head[maxn],id; void add_edge(int u,int v,int len) {edge[id].v = v;edge[id].len = len; edge[id].next = head[u];head[u] = id++;edge[id].v = u;edge[id].len = len; edge[id].next = head[v];head[v] = id++; } inline double max(double x,double y) {return x > y ? x : y; } void spfa(int s,int dis[]) {for(int i = 0; i <= n; i++)dis[i] = inf;memset(vis,0,sizeof(vis));queue<int>que;int now,tmp;dis[s] = 0;vis[s] = 1;que.push(s);while( !que.empty()){int u = que.front();que.pop();vis[u] = 0;for( int id = head[u]; id != -1; id = edge[id].next){int v = edge[id].v;if( v == p)continue;if( dis[v] > dis[u] + edge[id].len){dis[v] = dis[u] + edge[id].len;if( !vis[v]){vis[v] = 1;que.push(v);}}}} } bool dfs(int u,double speed) {if( Exit[u] )return true;for(int id = head[u]; id != -1; id = edge[id].next){int v = edge[id].v;if( !vis[v] && dis1[v]*1.0*160 < dis2[v]*speed){vis[v] = 1;if( dfs(v,speed) )return true;}}return false; } void slove() {double l = 0,r = 0,m;for(int i=1;i<=n;i++){if(!dis2[i] ) continue;r=max(r,(double)dis1[i]*160/dis2[i]);}double ans = -1;r += 2*(1e-7);while( r - l > 1e-7){m = (l+r)*0.5;memset(vis,0,sizeof( vis ));if(dfs(b,m)){r = m;ans = m;}else l = m;}if( ans < 0)puts("IMPOSSIBLE");elseprintf("%.10lf\n",ans); } int main() {int i,j,u,v,len;while( scanf("%d%d%d",&n,&m,&e) != EOF){memset(head,-1,sizeof(head));id = 0;while( m -- ){scanf("%d%d%d",&u,&v,&len);add_edge(u,v,len);}memset(Exit,0,sizeof(Exit));for( i = 0; i < e; i++){scanf("%d",&u);Exit[u] = 1;}scanf("%d%d",&b,&p);spfa(b,dis1);spfa(p,dis2);slove();}return 0; }/*3 2 1 1 2 7 2 3 8 1 3 2 3 2 1 1 2 7 2 3 8 1 2 3 4 4 2 1 4 1 1 3 4 3 4 10 2 3 30 1 2 3 4*/

轉載于:https://www.cnblogs.com/LUO257316/archive/2013/05/28/3220804.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU3143Speedy Escape 最短路+二分+搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。