[图论]红绿灯题解

啊哈磊

[图论]红绿灯题解[size=0.928571429]发表回复

红绿灯

【题目描述】
这一天Tom起晚了，为了更快的去上班，请帮他计算出一条最近的路线。Tom开车去工作，只有到了十字路口遇到红灯他才会停。那么他要多久才能到达公司呢？假设他的速度是1，并且当Tom出发的时候所有路口的灯都是红色。并且交通灯的红灯和绿灯同样长短，而且只有红绿两种颜色。Tom家门口和公司门口没有交通灯。

【输入】
第一行N（0 < N < 100）表示有N组测试数据。每一个测试数据第一行为整数M（0 < M < 100），接下来M行，每行包括像“a b 20 10”这样的数据。它表示Tom可以从a到b，a与b之间的距离为20，并且b处交通灯红灯（或绿灯）时长为10。每个测试样例的最后一行为Tom家和公司的名字，所有名字为小写字母。

【输出】
在一行中输出Tom使用的最短时间。

【样例输入】
1
4
t a 20 10
t b 10 9
b a 10 11
a c 20 0
t c

【样例输出】
40

【题解】
给出的题解是用dfs做的，但是本题应该用SPFA可以得到更好的效果

[code=Cpp width=740px]#include <stdio.h>
#define MAX 99999999
struct note
{
    int d;
    int t;
}E[27][27]={0};
int book[27]={0};

int start,end,min=MAX;

void dfs(int step,int time)
{
   
    int time1,i;
    printf("%d ",time);
   
    if(step==end)
    {
        if(time < min)
            min=time;
        return;
    }
    for(i=1; i<27;i++)
    {
        if(book==1)
            continue;
        if(E[step].d==MAX)
            continue;
        time1=time;
        time1+=E[step].d;
        if( E[step].t!=0 && time1 % (2*E[step].t) <  E[step].t )
            time1= time1 + ( E[step].t - time1 % (2*E[step].t) );
        book=1;
        dfs(i,time1);
        book=0;
    }
    return;
}

int main()
{
    freopen("test1.in","r",stdin);
    freopen("test1.out","w",stdout);
    int n,m,i,j,x,y;
    char ch1,ch2;
    scanf("%d",&n);
    getchar();
    for(i=1;i < 27;i++)
        for(j=1;j < 27;j++)
        {
            if(i==j)
            {
                E[j].d=MAX;
                E[j].t=MAX;
            }
            else
            {
                E[j].d=MAX;
                E[j].t=MAX;
            }
        }
        
    for(i=1;i <= n;i++)
    {
        scanf("%c %c %d %d",&ch1,&ch2,&x,&y);
        getchar();
        E[ch1-'a'+1][ch2-'a'+1].d=x;
        E[ch1-'a'+1][ch2-'a'+1].t=y;
    }
   
    scanf("%c %c",&ch1,&ch2);
    start=ch1-'a'+1;
    end=ch2-'a'+1;
   
    book[start]=1;
    dfs(start,0);
   
    printf("%d",min);
    return 0;
}
</stdio.h>[/code]