POJ1135 Domino Effect

题目：http://poj.org/problem?id=1135

只是求以1为起点的最短路罢了。稍稍判断一下在边上的情况。

多亏提醒：毒数据——n==1！一定要dis [ k ] >= ans！！！

注意输出格式（换行）。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

int n,m,head[],xnt,x,y,T;

int hp[],cnt,k1,k2;

ll dis[],z;

double ans;

bool vis[];

struct Edge{

    int next,to;

    ll w;

    Edge(int a=,int b=,ll c=):next(a),to(b),w(c) {}

}edge[];

ll abss(ll k)

{

    if(k<)k=-k;

    return k;

}

void push(int k)

{

    hp[++cnt]=k;

    int now=cnt;

    while(now>)

    {

        int tp=(now>>);

        if(dis[hp[now]]<dis[hp[tp]])swap(hp[now],hp[tp]);

        else break;

        now=tp;

    }

}

int del()

{

    int res=hp[];

    hp[]=hp[cnt--];

    int now=;

    while((now<<)<=cnt)

    {

        int tp=(now<<);

        if(tp<cnt&&dis[hp[tp+]]<dis[hp[tp]])tp++;

        if(dis[hp[tp]]<dis[hp[now]])swap(hp[tp],hp[now]);

        else break;

        now=tp;

    }

    return res;

}

int main()

{

    while(++T)

    {

        scanf("%d%d",&n,&m);

        if(!n&&!m)return ;

        memset(dis,,sizeof dis);

        memset(head,,sizeof head);

        memset(vis,,sizeof vis);

        xnt=;ans=;k1=;k2=;

        for(int i=;i<=m;i++)

        {

            scanf("%d%d%lld",&x,&y,&z);

            edge[++xnt]=Edge(head[x],y,z);head[x]=xnt;

            edge[++xnt]=Edge(head[y],x,z);head[y]=xnt;

        }

        dis[]=;push();

        while(cnt)

        {

            int k=del();

            while(cnt&&vis[k])k=del();

            if(vis[k])break;

            vis[k]=;

            if(dis[k]>=ans)//////////

            {

                ans=dis[k];k1=k;

            }

            for(int i=head[k],v;i;i=edge[i].next)

                if(!vis[v=edge[i].to]&&dis[k]+edge[i].w<dis[v])

                {

                    dis[v]=dis[k]+edge[i].w;

                    push(v);

                }

        }

        double c=;

        for(int i=;i<=n;i++)

            for(int j=head[i],v;j;j=edge[j].next)

                if(abss(dis[i]-dis[v=edge[j].to])<edge[j].w&&

                    (c=max(dis[i],dis[v])+(double)(edge[j].w-abss(dis[i]-dis[v]))/)>ans)

                    {

                        ans=c;k1=min(i,v);k2=max(i,v);

                    }

        printf("System #%d\n",T);

        if(!k2)

            printf("The last domino falls after %.1lf seconds, at key domino %d.\n\n",ans,k1);

        else

            printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n\n",ans,k1,k2);

    }

}