HDU-3143-Speedy Escape(最短路+路径记录)

The Newton brothers are planning to rob a bank in the city of Alviso and want to figure out a way to escape the city‘s only police car. They know that their car is faster than the police car so if they could just reach one of the highways exiting the city they will be able to speed away from the police.

The police car has a maximum speed of 160 km/h. Luckily, the brothers know where the police car will start (it‘s parked at the police station). To be on the safe side they assume that the police car will start moving as soon as they leave the bank and start their car (this is when the alarm goes off).

The brothers want to find a fixed route that ensures that they are able to leave the city no matter what route the police car take and at what speed it drives. However, since the brothers are not very confident drivers they don‘t want to drive faster than necessary. Luckily they have recently invested in a new hi-tech in-car police escape system that you have constructed. This system will tell them what the minimal top speed needed to escape is (and probably other useful things like what route to take).

Let‘s turn the clock back a bit to the time when you were constructing the escape system and focused on finding the minimal required speed. Can you get it right?

You may treat all roads as infinitesimally narrow and both cars as point objects. If the brothers ever end up at the same point (on any road or intersection) at the same time as the police car they will be caught and by Murphy‘s law if there is any possibility of this happening it will happen. The two cars start simultaneously and can accelerate/decelerate instantaneously at any time to any speed below or equal to its maximum speed. They can also change roads at intersections or direction anywhere on a road instantaneously no matter what speed they are traveling at.

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

IMPOSSIBLE
74.6666666667
137.142857143

思路：首先用Dijkstra求出抢劫犯绕过警察所在起点到各个终点的最短路dp[i]并记录其路径。再求出警察到各个点的最短路dq[i]。 判断有无结果的话，就直接看所有dp[i]，如果都是INF就无结果。 如果有结果就查找所有能到达终点的路径，找最小速度。 （这里只用了带路径记录的Dijkstra，具体看代码）

#include <cstdio>
#include <algorithm>
#define INF 9999999
using namespace std;

int map[101][101],des[101],n,m,e,p,q,dp[101],dq[101],vis[101],son[101];

int main()
{
    int i,j,ta,tb,tc,minindex,minnum,temp;

    while(~scanf("%d%d%d",&n,&m,&e))
    {
        for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=INF;

        while(m--)
        {
            scanf("%d%d%d",&ta,&tb,&tc);

            map[ta][tb]=map[tb][ta]=tc;
        }

        for(i=0;i<e;i++)
        {
            scanf("%d",&des[i]);
        }

        scanf("%d%d",&p,&q);

        for(i=1;i<=n;i++) son[i]=0,vis[i]=0,dp[i]=INF;
        dp[p]=0;

        ta=n-2;//抢劫犯绕开警察到各点的最小距离
        while(ta--)
        {
            minnum=INF;
            for(i=1;i<=n;i++)
            {
                if(!vis[i] && dp[i]<minnum && i!=q)
                {
                    minnum=dp[i];
                    minindex=i;
                }
            }

            if(minnum==INF) break;
            vis[minindex]=1;

            for(i=1;i<=n;i++)
            {
                if(!vis[i] && dp[i]>dp[minindex]+map[minindex][i] && i!=q)
                {
                    dp[i]=dp[minindex]+map[minindex][i];
                    son[i]=minindex;//记录路径
                }
            }
        }

        for(i=1;i<=n;i++) vis[i]=0,dq[i]=INF;
        dq[q]=0;

        ta=n-1;//警察到各点的最小距离
        while(ta--)
        {
            minnum=INF;
            for(i=1;i<=n;i++)
            {
                if(!vis[i] && dq[i]<minnum)
                {
                    minnum=dq[i];
                    minindex=i;
                }
            }

            if(minnum==INF) break;
            vis[minindex]=1;

            for(i=1;i<=n;i++)
            {
                if(!vis[i] && dq[i]>dq[minindex]+map[minindex][i])
                {
                    dq[i]=dq[minindex]+map[minindex][i];
                }
            }
        }

        for(i=0;i<e;i++)//判断有没有可能逃跑
        {
            if(dp[des[i]]<INF)
                break;

        }

        if(i==e)
        {
            printf("IMPOSSIBLE\n");
        }
        else
        {
            double ans=INF;

            for(i=0;i<e;i++)//枚举每一个终点
            {
                if(dp[des[i]]<INF)//如果终点可行
                {
                    double temp=0;//用来临时保存这个终点的最小速度

                    ta=des[i];
                    while(son[ta])//枚举到达该终点的路径
                    {
                        if(dq[ta]<INF)
                        {
                            temp=max(temp,(double)dp[ta]/dq[ta]*160.0);//对于每一个路径，如果警察可以到达就算出满足这一个点需要的最小速度
                        }

                        ta=son[ta];
                    }

                    ans=min(ans,temp);
                }


            }

            printf("%.10lf\n",ans);
        }
    }
}

HDU-3143-Speedy Escape(最短路+路径记录),布布扣,bubuko.com

HDU-3143-Speedy Escape(最短路+路径记录)

原文：http://blog.csdn.net/faithdmc/article/details/23223273