Vladimir has white skin, very long teeth and is 600 years old, but this is no problem because Vladimir is a vampire.
Vladimir has never had any problems with being a vampire. In fact, he is a very successful doctor who always takes the night shift and so has made many friends among his colleagues. He has a very impressive trick which he shows at dinner partys: He can tell tell blood group by taste.
Vladimir loves to travel, but being a vampire he has to overcome three problems.

• First, he can only travel by train because he has to take his coffin with him. (On the up side he can always travel first class because he has invested a lot of money in long term stocks.)
• Second, he can only travel from dusk till dawn, namely from 6 pm to 6 am. During the day he has to stay inside a train station.
• Third, he has to take something to eat with him. He needs one litre of blood per day, which he drinks at noon (12:00) inside his coffin.

Input Specification

Output Specification

Sample Input

2
3
Ulm Muenchen 17 2
Ulm Muenchen 19 12
Ulm Muenchen 5 2
Ulm Muenchen
10
Lugoj Sibiu 12 6
Lugoj Sibiu 18 6
Lugoj Sibiu 24 5
Lugoj Medias 22 8
Lugoj Medias 18 8
Lugoj Reghin 17 4
Sibiu Reghin 19 9
Sibiu Medias 20 3
Reghin Medias 20 4
Reghin Bacau 24 6
Lugoj Bacau
    

Sample Output

Test Case 1.
There is no route Vladimir can take.
Test Case 2.
Vladimir needs 2 litre(s) of blood.
    

題目描述：
吸血鬼 弗萊迪米爾，搭乘火車從出發到目的地，他可以在晚上六點到早上六點在火車上，
而其他時間他必須待在火車站，而每天中午十二點，他會飲用一公升的鮮血，給火車時刻表，
從起點幾點發車，經過幾個小時後抵達目的火車站。求最少攜帶的鮮血。

題目解法：
先將不可能的火車班次給去除掉，接著用最短路跑一次，更新的時候多一個抵達時間的狀態。


#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
struct edge {
    int to, l, r;
    edge(int a, int b, int c):
        to(a), l(b), r(c) {}
};
vector<edge> g[205];
void spfa(int st, int ed) {
    int dist[205][35];//18:00-30:00
    int inq[205][35] = {};
    memset(dist, 63, sizeof(dist));
    int oo = dist[0][0];
    int i, j, k, w;
    for(i = 0; i < 35; i++)
        dist[st][i] = 0;
    queue<int> Qn, Qt;
    Qn.push(st), Qt.push(18);
    while(!Qn.empty()) {
        int tn = Qn.front();
        int tt = Qt.front();
        Qn.pop(), Qt.pop();
        inq[tn][tt] = 0;
        for(vector<edge>::iterator it = g[tn].begin();
            it != g[tn].end(); it++) {
            if(it->l >= tt)
                w = 0;
            else
                w = 1;
            if(dist[it->to][it->r] > dist[tn][tt] + w) {
                dist[it->to][it->r] = dist[tn][tt] + w;
                if(inq[it->to][it->r] == 0) {
                    inq[it->to][it->r] = 1;
                    Qn.push(it->to), Qt.push(it->r);
                }
            }
        }
    }
    int ret = oo;
    for(i = 0; i < 35; i++)
        ret = min(ret, dist[ed][i]);
    if(ret == oo)
        puts("There is no route Vladimir can take.");
    else
        printf("Vladimir needs %d litre(s) of blood.\n", ret);
}
int main() {
    int testcase, cases = 0;
    int n, i, j;
    char s1[105], s2[105];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        map<string, int> R;
        for(i = 0; i < 200; i++)
            g[i].clear();
        int size = 0;
        while(n--) {
            int stime, htime;
            scanf("%s %s %d %d", s1, s2, &stime, &htime);
            int &x = R[s1];
            int &y = R[s2];
            if(x == 0)  x = ++size;
            if(y == 0)  y = ++size;
            if(stime < 6)   stime += 24;
            if(stime + htime > 24 + 6 || stime < 18)
                continue;
            g[x].push_back(edge(y, stime, stime+htime));
        }
        scanf("%s %s", s1, s2);
        printf("Test Case %d.\n", ++cases);
        int &x = R[s1];
        int &y = R[s2];
        if(x == 0)  x = ++size;
        if(y == 0)  y = ++size;
        spfa(x, y);
    }
    return 0;
}