学步园

POJ 1135 Domino Effect(Dijkstra)

http://poj.org/problem?id=1135

题意: 有一些多米若骨牌,其中有一些关键牌.(这些关键牌可以看成无向图的顶点,关键牌之间的普通牌看成是无向图的边). 然后构成了一个具有n个点,m条边的无向图,每条边有行走时间.现在问你最后倒下的骨牌是不是关键牌,且时间是多少?

分析:

       最后倒下的骨牌只有两种情况:关键牌或者非关键牌.

       由于骨牌都是从1号骨牌开始倒下的,所以我们只需要算出从1点到其他所有点的距离即可算出,其他关键骨牌的倒塌时间的最大值MAX_1.(想想是不是)

       然后我们要算出m条边中(包括两端点)的最晚倒塌的骨牌的时间是多少? 对于a点与b点构成的边,假设a点在d[a]倒塌,b点在d[b]倒塌,且边(a,b)的权值(时间)为 edges[i].dist,所以该边中骨牌的最晚倒塌时间为: (d[a]+d[b]+edges[i].dist)/2 (仔细想想是不是)  记录最大的这种值MAX_2且记录该值对应的两个端点编号.

       如果MAX_1 < MAX_2,说明最后倒塌的是普通骨牌.

       如果MAX_1>=MAX_2,说明最后倒塌的是关键骨牌.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn= 500+10;
int n,m;
struct Edge
{
    int from,to;
    double dist;
    Edge(){}
    Edge(int from,int to,double d):from(from),to(to),dist(d){}
}e[maxn*maxn];
struct HeapNode
{
    double dist;
    int u;
    HeapNode(double dist,int u):dist(dist),u(u){}
    bool operator < (const HeapNode &rhs) const
    {
        return dist > rhs.dist;
    }
};
struct Dijkstra
{
    int n,m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];
    double d[maxn];

    void init(int n)
    {
        this->n=n;
        for(int i=0;i<n;i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from,int to,double dist)
    {
        edges.push_back(Edge(from,to,dist) );
        m=edges.size();
        G[from].push_back(m-1);
    }

    void dijkstra()
    {
        priority_queue<HeapNode> Q;
        for(int i=0;i<n;i++) d[i]= 1e15;
        d[0]=0.0;
        Q.push(HeapNode(d[0],0));
        memset(done,0,sizeof(done));

        while(!Q.empty())
        {
            HeapNode x=Q.top(); Q.pop();
            int u =x.u;
            if(done[u]) continue;
            done[u]=true;

            for(int i=0;i<G[u].size();i++)
            {
                Edge &e=edges[G[u][i]];
                if(d[e.to] > d[u]+e.dist)
                {
                    d[e.to] = d[u]+e.dist;
                    Q.push(HeapNode(d[e.to],e.to));
                }
            }
        }
    }
}DJ;
int main()
{
    int kase=1;
    while(scanf("%d%d",&n,&m)==2&&n)
    {
        DJ.init(n);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%lf",&e[i].from,&e[i].to,&e[i].dist);
            e[i].from--;
            e[i].to--;
            DJ.AddEdge(e[i].from,e[i].to,e[i].dist);
            DJ.AddEdge(e[i].to,e[i].from,e[i].dist);
        }
        DJ.dijkstra();

        double max_v1=-1;
        int max_v1_point;
        for(int i=0;i<n;i++)if(max_v1 < DJ.d[i])
        {
            max_v1 = DJ.d[i];
            max_v1_point = i;
        }

        double max_v2=-1;
        int max_v2_p1,max_v2_p2;
        for(int i=0;i<m;i++)
        {
            int u=e[i].from, v=e[i].to, dist=e[i].dist;
            if(max_v2 < (DJ.d[u]+DJ.d[v]+dist)/2)
            {
                max_v2 = (DJ.d[u]+DJ.d[v]+dist)/2;
                max_v2_p1 = min(u,v);
                max_v2_p2 = max(u,v);
            }
        }

        if(max_v1 < max_v2)
        {
            printf("System #%d\nThe last domino falls after ",kase++);
            printf("%.1lf seconds, between key dominoes %d and %d.\n\n",max_v2,max_v2_p1+1,max_v2_p2+1);
        }
        else
        {
            printf("System #%d\nThe last domino falls after ",kase++);
            printf("%.1lf seconds, at key domino %d.\n\n",max_v1,max_v1_point+1);
        }
    }
    return 0;
}