题目大意：有n个城市m条航线。给出每条航线的出发地，目的地，座位数，起飞时间和到达时间(所给形式为HHMM。记得转化)，再给出城市A和B。和到达城市B的最晚时间。如今问一天内最多有多少人能从A飞到B，能够在其它城市中转

解题思路：将飞机票拆点，拆成i–>i ＋ m,容量为座位数。

接着推断一下。航线之间的连线

假设航线的起点是A的话，那么就和超级源点相连，容量为INF

假设航线的终点是B且到达时间小于等于最晚时间。那么连线，容量为INF

假设航线i的终点和航线j的起点同样。且航线i的到达时间+30<=航线j的起始时间，那么连线。容量为INF

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#include <iostream>

using namespace std;

#define N 10010

#define INF 0x3f3f3f3f

struct Edge{

    int from, to, cap, flow;

    Edge() {}

    Edge(int from, int to, int cap, int flow) : from(from), to(to), cap(cap), flow(flow) {}

};

struct Dinic{

    int n, m, s, t;

    vector<Edge> edges;

    vector<int> G[N];

    bool vis[N];

    int d[N], cur[N];

    void init(int n) {

        this->n = n;

        for (int i = 0; i <= n; i++) {

            G[i].clear();

        }

        edges.clear();

    }

    void AddEdge(int from, int to, int cap) {

        edges.push_back(Edge(from, to, cap, 0));

        edges.push_back(Edge(to, from, 0, 0));

        int m = edges.size();

        G[from].push_back(m - 2);

        G[to].push_back(m - 1);

    } 

    bool BFS() {

        memset(vis, 0, sizeof(vis));

        queue<int> Q;

        Q.push(s);

        vis[s] = 1;

        d[s] = 0;

        while (!Q.empty()) {

            int u = Q.front();

            Q.pop();

            for (int i = 0; i < G[u].size(); i++) {

                Edge &e = edges[G[u][i]];

                if (!vis[e.to] && e.cap > e.flow) {

                    vis[e.to] = true;

                    d[e.to] = d[u] + 1;

                    Q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int DFS(int x, int a) {

        if (x == t || a == 0)

            return a;

        int flow = 0, f;

        for (int i = cur[x]; i < G[x].size(); i++) {

            Edge &e = edges[G[x][i]];

            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {

                e.flow += f;

                edges[G[x][i] ^ 1].flow -= f;

                flow += f;

                a -= f;

                if (a == 0)

                    break;

            }

        }

        return flow;

    }

    int Maxflow(int s, int t) {

        this->s = s; this->t = t;

        int flow = 0;

        while (BFS()) {

            memset(cur, 0, sizeof(cur));

            flow += DFS(s, INF);

        }

        return flow;

    }

};

Dinic dinic;

#define M 5100

#define S 160

int n, m, source, sink, Time;

int num[S];

map<string, int> Map;

struct Node {

    int u, v, c, s, t;

}node[M];

int getTime(string T) {

    int a = (T[0] - '0') * 10 + (T[1] - '0');

    int b = (T[2] - '0') * 10 + (T[3] - '0');

    return a * 60 + b;

}

void solve() {

    Map.clear();

    int cnt = 3;

    string a, b, s, t;

    cin >> a >> b >> s >> m;

    Map[a] = 1; Map[b] = 2;

    Time = getTime(s);

    memset(num, 0, sizeof(num));

    source = 0; sink = 2 * m + 1;

    dinic.init(sink);

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

        cin >> a >> b >> node[i].c >> s >> t;

        if (!Map[a]) Map[a] = cnt++;

        if (!Map[b]) Map[b] = cnt++;

        node[i].u = Map[a];

        node[i].v = Map[b];

        node[i].s = getTime(s);

        node[i].t = getTime(t);

        num[node[i].u]++; num[node[i].v]++;

        dinic.AddEdge(i, i + m, node[i].c);

    }

    if (!num[1] || !num[2]) {

        printf("0\n");

        return ;

    }

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

        int u = node[i].u, v = node[i].v;

        if (u == 1) dinic.AddEdge(source, i, INF);

        if (v == 2 && node[i].t <= Time) dinic.AddEdge(i + m, sink, INF);

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

            if (i == j) continue;

            if (v != node[j].u) continue;

            if (node[i].t + 30 <= node[j].s) dinic.AddEdge(i + m, j, INF);

        }

    }

    int ans = dinic.Maxflow(source, sink);

    printf("%d\n", ans);

}

int main() {

    while (scanf("%d\n", &n) != EOF)  solve();

    return 0;

}