zoj1956.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
#include <map>
#include <string>
using namespace std;

int n, m, es;
map<string, int> tb;
struct Edge{
    int s, t;
    int u, v;   
} e[1010];
int d[200];

int find(string s){
    if (tb.count(s)) return tb[s];
    tb[s] = n++;
    return tb[s];   
}

bool finish;
void update(int x){
    if (d[e[x].u] < 0x3fffffff){
        if (d[e[x].u] % 24 > e[x].s && d[e[x].v] > (d[e[x].u]/24+1)*24 + e[x].t){
            finish = false;
            d[e[x].v] = (d[e[x].u]/24+1)*24 + e[x].t;
        }
        if (d[e[x].u] % 24 <= e[x].s && d[e[x].v] > (d[e[x].u]/24)*24 + e[x].t){
            finish = false;
            d[e[x].v] = (d[e[x].u]/24)*24 + e[x].t;
        }
    }   
}

int main(){
    int cases;  scanf("%d", &cases);
    char s1[100], s2[100];
    for (int tc = 1; tc <= cases; tc++){
        scanf("%d", &m);
        n = 0;  tb.clear();
        int ut;  es = 0;
        while (m--){
            scanf("%s %s %d %d", s1, s2, &e[es].s, &ut);
            e[es].u = find(s1);
            e[es].v = find(s2);
            
            if (ut > 12) continue;
            if (e[es].s >= 6 && e[es].s < 18) continue;
            if ( (e[es].s + ut) % 24 > 6 && (e[es].s + ut) % 24 < 18) continue;
            e[es].s -= 18;
            if (e[es].s < 0) e[es].s += 24;
            e[es].t = e[es].s + ut;
            es++;
        }
        scanf("%s %s", s1, s2);
        for (int i = 0; i < n; i++) d[i] = 0x3fffffff; 
        d[find(s1)] = 0;
        int dst = find(s2);
        while (1){
            finish = true;
            for (int j = 0; j < es; j++) update(j);
            if (finish) break;
            //if (d[dst] < 0x3fffffff) break;
        }
        printf("Test Case %d.\n", tc);
        dst = d[dst];
        if (dst == 0x3fffffff) printf("There is no route Vladimir can take.\n");
        else printf("Vladimir needs %d litre(s) of blood.\n", dst/24);
    }   
    return 0;   
}