Problem F.Travel

Background

Xiao Ming, a clever and lazy boy, is good at programming and sleeping. He hated traveling by train very much. Nevertheless, tomorrow in the early morning hours he will travel from Liuzhou to Xi’an to in order to get to the National Olympiad of Informatics in 2001 (NOI2001). Since he is afraid of arriving too late and being excluded from the contest, he is looking for the train which gets her to Xi’an as early as possible. However he dislikes getting to the station too early, so if there are several schedules with the same arrival time, he will choose the one with the latest departure time.

Xiao Ming asks you to help him with his problem, so that she can sleep a bit longer tomorrow. You are given a set of railroad schedules from which you have to compute the fastest connection among those with the earliest arrival time for going from one location to another. One good thing: Xiao Ming can switch trains in zero time.

Input

The input file contains several scenarios. Each of them consists of 3 parts:

Part one lists the names of all cities connected by the railroads. It starts with a line containing an integer C(1<=C<=100) followed by C lines containing city names. These names consist of at most 20 letters.

Part two describes all the trains running during the day. It start with a number T<=100 followed by T train descriptions. Each train description consists of one line with a number ti<100 and ti more lines with a time and a city name, meaning that passengers can get on or off the train at that time at that city. The times are given in the 24-hour format hhmm.

Part three consists of three lines: Line one contains the earliest possible starting time for the journey, line two the name of the city where he starts, and line three the destination city. The two cities are always different.

The end of the input file is marked by a line containing only a zero(instead of C). Do not process this line.

Output

For each scenario print one line solution. If a connection exists the print 2 four-digit numbers, meaning hhmm, the starting time and the arriving time. If not connection exists print a line containing “No connection”.

Sample Input

Liuzhou

Guilin

Xian

0900 Liuzhou

1200 Guilin

2200 Xian

0900 Liuzhou

1200 Guilin

2300 Xian

0800

Liuzhou

Xian

Liuzhou

Guilin

Xian

0900 Liuzhou

1200 Guilin

2300 Xian

1000

Liuzhou

Xian

Sample Output

0900 2200

No connection

題目描述：

給定火車時刻表，找到一個最早到達時，最晚出發的時刻。

題目解法：

dp[i][j], 表示在時間 i 抵達 j 站得最晚出發時間。
進行轉移即可。由於 i <= 2400, 跑起來很慢的。

#include <stdio.h>
#include <string.h>
#include <map>
#include <vector>
#include <iostream>
using namespace std;
int dp[2405][105];
struct E {
    int st, ed, to;
    E(int a, int b, int c):
        st(a), ed(b), to(c) {}
};
vector<E> g[105];
int main() {
    int n, m, q;
    char s[105];
    int i, j, k;
    while(scanf("%d", &n) == 1 && n) {
        map<string, int> R;
        for(i = 0; i < n; i++) {
            scanf("%s", s);
            R[s] = i;
            g[i].clear();
        }
        memset(dp, -1, sizeof(dp));
        scanf("%d", &m);
        while(m--) {
            scanf("%d", &q);
            int pret, pren, time, tn;
            scanf("%d %s", &time, s), q--;
            pret = (time/100)*60 + time%100;
            pren = R[s];
            while(q--) {
                scanf("%d %s", &time, s);
                time = (time/100)*60 + time%100;
                tn = R[s];
                g[pren].push_back(E(pret, time, tn));
                pren = tn, pret = time;
            }
        }
        int st, ed, stime;
        scanf("%d %s", &stime, s);
        st = R[s];
        scanf("%s", s);
        ed = R[s];
        stime = stime/100*60 + stime%100;
        int ll = -1, rr;
        for(i = stime; i <= 2400; i++) {
            for(j = 0; j < n; j++) {
                for(k = 0; k < g[j].size(); k++) {
                    if(g[j][k].st < i) continue;
                    if(j == st)
                        dp[i][j] = g[j][k].st;
                    dp[g[j][k].ed][g[j][k].to] = max(dp[g[j][k].ed][g[j][k].to], dp[i][j]);
                }
            }
            if(dp[i][ed] != -1) {
                ll = dp[i][ed];
                rr = i;
                break;
            }
        }
        if(ll == -1)
            puts("No connection");
        else
            printf("%02d%02d %02d%02d\n", ll/60, ll%60, rr/60, rr%60);

    }
    return 0;
}

我要檢舉

#10166#Travel

台長： Morris

您可能對以下文章有興趣

[UVA][SPFA&DP][C++] 11813 - Shopping

[UVA][floyd] 10793 - The Orc Attack

[UVA] 11835 - Formula 1

[UVA][空間幾何] 10495 - Conic Distance

人氣(2,749) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 11833 - Route Change
此分類上一篇:[UVA] 949 - Getaway

回應(0)