gohome.c

ACM中春运中的烦恼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 320
#define MAXNUM 2147483647

#define Min(x,y) (x<y?x:y)


void initialize (void);
int getcolor (int x,int time);
void work (void);
void print (int x);


int rest;
int n,m,f,t;

int a[SIZE][SIZE];
int st[SIZE],sc[SIZE],bt[SIZE],pt[SIZE],tt[SIZE],u[SIZE],w[SIZE],l[SIZE];


int main (void)
{
    while (scanf("%d%d",&n,&m)==2)
    {
        initialize ();
        work ();
    }

    return 0;
}


void initialize (void)
{
    char color[10];
    int i,x,y,z;

    memset (a,0,sizeof(a));
    memset (u,0,sizeof(u));
    memset (w,0,sizeof(w));

    scanf ("%d%d",&f,&t);
    for (i=1;i<=n;i++)
    {
        scanf ("%s%d%d%d",color,&st[i],&bt[i],&pt[i]);
        sc[i]=color[0]-'0';
        tt[i]=bt[i]+pt[i];
    }

    for (i=1;i<=m;i++)
    {
        scanf ("%d%d%d",&x,&y,&z);
        a[x][y]=a[y][x]=z;
    }
}


int getcolor (int x,int time)
{
    if (time<st[x])
    {
        rest=st[x]-time;
        return sc[x];
    }

    time=(time-st[x])%tt[x];
    
    if (sc[x])
    {
        if (time<bt[x])
        {
            rest=bt[x]-time;
            return 0;
        }

        rest=tt[x]-time;
        return 1;
    }

    if (time<pt[x])
    {
        rest=pt[x]-time;
        return 1;
    }

    rest=tt[x]-time;
    return 0;
}


void work (void)
{
    int i,j,k,min;
    int c1,ck;
    int r1,r2,rk,rk2;

    for (i=1;i<=n;i++)
        w[i]=MAXNUM;

    w[f]=0;
    for (i=1;i<=n;i++)
    {
        min=MAXNUM;
        
        for (j=1;j<=n;j++)
            if (!u[j])
                if (min>w[j])
                {
                    min=w[j];
                    k=j;
                }

        u[k]=1;
        ck=getcolor (k,w[k]);
        rk=rest;
        getcolor (k,w[k]+rest);
        rk2=rest;

        for (j=1;j<=n;j++)
            if (a[k][j])
            {
                c1=getcolor (j,w[k]);
                r1=rest;
            
                if (c1==ck)
                {
                    if (w[j]>w[k]+a[k][j])
                    {
                        w[j]=w[k]+a[k][j];
                        l[j]=k;
                    }
                }
                else
                {
                    if (r1!=rk)
                    {
                        if (w[j]>w[k]+a[k][j]+Min(r1,rk))
                        {
                            w[j]=w[k]+a[k][j]+Min(r1,rk);
                            l[j]=k;
                        }
                    }
                    else
                    {
                        getcolor (j,w[k]+r1);
                        r2=rest;

                        if (r2!=rk2)
                            if (w[j]>w[k]+a[k][j]+r1+Min(r2,rk2))
                            {
                                w[j]=w[k]+a[k][j]+r1+Min(r2,rk2);
                                l[j]=k;
                            }
                    }
                }
            }
    }

    if (w[t]==MAXNUM)
        printf ("Poor OIBen.\n");
    else
    {
        printf ("%d\n",w[t]);
        print (t);
        printf ("\n");
    }
}


void print (int x)
{
    if (x==f)
    {
        printf ("%d",x);
        return;
    }

    print (l[x]);
    printf (" %d",x);
}