HDU 2722 Here We Go(relians) Again

最短路，建图太麻烦，略过……
#include <cstdio>

#include <cstring>

#include <queue>

const int INF=9999999;

using namespace std;

struct node{

    int v,i;

    node(int a,int b){v=a,i=b;}

    bool operator <(const node& a)const{return v>a.v;}

};

int n,m,map[500][500];

int done[500],d[500];

int dij(){

    priority_queue q;

    memset(done,0,sizeof done);

    for(int i=1;i<=(n+1)*(m+1);i++)d[i]=INF;

    d[1]=0;

    q.push(node(d[1],1));

    while(!q.empty()){

        node nd=q.top();q.pop();

        int u=nd.i;

        if(done[u])continue;

        done[u]=1;

        for(int i=1;i<=(n+1)*(m+1);i++){

            if(d[i]>d[u]+map[u][i]){

                d[i]=d[u]+map[u][i];

                q.push(node(d[i],i));

            }

        }

    }

    if(d[(n+1)*(m+1)]==INF)return -1;

    else return d[(n+1)*(m+1)];

}

int main(){

    char s[3];int v;

    while(scanf("%d%d",&n,&m),n||m){

        for(int i=1;i<=(n+1)*(m+1);i++)for(int j=1;j<=(n+1)*(m+1);j++)map[i][j]=INF;

        int n1,n2;

        for(int i=1;i<=2*n+1;i++){

            if(i%2==1){

                for(int j=1;j<=m;j++){

                    n1=(i/2)*(m+1)+j,n2=n1+1;

                    scanf("%d%s",&v,s);

                    if(v==0)continue;

                    if(s[0]=='*')map[n1][n2]=map[n2][n1]=2520/v;

                    else if(s[0]=='<')map[n2][n1]=2520/v;

                    else if(s[0]=='>')map[n1][n2]=2520/v;

                }

            }else{

                for(int j=1;j<=m+1;j++){

                    n1=(i/2-1)*(m+1)+j,n2=n1+m+1;

                    scanf("%d%s",&v,s);

                    if(v==0)continue;

                    if(s[0]=='*')map[n1][n2]=map[n2][n1]=2520/v;

                    else if(s[0]=='v')map[n1][n2]=2520/v;

                    else if(s[0]=='^')map[n2][n1]=2520/v;

                }

            }

        }

        int r=dij();

        if(r==-1)printf("Holiday\n");

        else printf("%d blips\n",r);

    }

    return 0;

}
巴特西

HDU 2722 Here We Go(relians) Again

最新文章

热门文章
