程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1135 Domino Effect

poj 1135 Domino Effect

編輯：C++入門知識

dijkstra算法的應用。

我的思路：先找到從第一個點出發到所有點的單源最短路，選擇最長的一個。如果某兩個點之間的多米諾骨牌傳播時間終止點在最長的最短路時間之後，就把該點確定為所需時間。

用“printf” G++ wa,C++ac.

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define maxn 505
#define maxm 30005
#define INF 1<<25
typedef long long ll;
using namespace std;
int point [maxn];
int vv[maxn];
double dis[maxn];
struct Edge
{
    int v;
    double w;
    int next;
} edge[maxm];
int top;
int init()
{
    top=0;
    memset(point,-1,sizeof(point));
    return 0;
}
int add_edge(int x,int v,double w)
{
    edge[top].v=v;
    edge[top].w=w;
    edge[top].next=point[x];
    point[x]=top++;
    edge[top].v=x;
    edge[top].w=w;
    edge[top].next=point[v];
    point[v]=top++;
    return 0;
}
struct node
{
    int v,w;
    node(int _v,int _w):v(_v),w(_w) {}
    bool operator < (const node &a)const
    {
        return a.w qq;
        memset(vv,0,sizeof(vv));
        for(int i=1; i<=tot; i++)
        {
            dis[i]=INF;
        }
        dis[1]=0;
        qq.push(node(1,0));
        printf("System #%d\n",jj++);
        while(!qq.empty())
        {
            node rec=qq.top();
            qq.pop();

            if(vv[rec.v]==1)
                continue;
            vv[rec.v]=1;
            for(int i=point[rec.v]; i!=-1; i=edge[i].next)
            {
                int v=edge[i].v;
                int w=edge[i].w;
                if(dis[v]>dis[rec.v]+edge[i].w&&dis[rec.v]!=INF)
                {
                    dis[v]=dis[rec.v]+edge[i].w;
                    qq.push(node(v,dis[v]));
                }

            }
        }
        for(int i=2; i<=tot; i++)
        {
            if(dis[i]>ans)
            {
                ans=dis[i];
                ra=i;
            }
        }
        for(int ii=1; ii<=tot; ii++)
        {
            for(int i=point[ii]; i!=-1; i=edge[i].next)
            {
                int v=edge[i].v;
                int w=edge[i].w;
                if(dis[ii]<=dis[v])
                {
                    double num=dis[v]+(w+dis[ii]-dis[v])/2;
                    if(num>ans)
                    {
                        jud=1;
                        aa=ii;
                        bb=v;
                        ans=num;
                    }
                }
            }
        }
        if(jud==0)
            printf("The last domino falls after %.1lf seconds, at key domino %d.\n",ans,ra);
        else
        {
            if(aa>bb) swap(aa,bb);
            printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n",ans,aa,bb);
        }
        printf("\n");
    }
}