Problem A: Railroads

Background 

It's Friday evening and Jill hates two things which are common to all trains:

1.

They are always late.

2.

The schedule is always wrong.

Nevertheless, tomorrow in the early morning hours Jill will have to travel from Hamburg to Darmstadt in order to get to the regional programming contest. Since she is afraid of arriving too late and being excluded from the contest she is looking for the train which gets her to Darmstadt as early as possible. However, she dislikes to get to the station too early, so if there are several schedules with the same arrival time then she will choose the one with the latest departure time.

Problem 

Jill asks you to help her with her problem. You are given a set of railroad schedules from which you must compute the train with the earliest arrival time and the fastest connection from one location to another. One good thing: Jill is very experienced in changing trains. She can do this instantaneously, i.e., in zero time!!!

Input 

The very first line of the input gives the number of scenarios. Each scenario consists of three parts.

Part one lists the names of all cities connected by the railroads. It starts with a number , followed by C lines containing city names. These names consist of letters.

Part two describes all the trains running during a day. It starts with a number followed by T train descriptions. Each of them consists of one line with a number and t_i 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.

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

Output 

For each scenario print a line containing ``Scenario i'', where i is the number of the scenario starting at 1.

If a connection exists then print the two lines containing zero padded timestamps and locations as shown in the sample. Use blanks to achieve the indentation. If no connection exists on the same day (i.e., arrival before midnight) then print a line containing ``No connection''.

After each scenario print a blank line.

Sample Input 

2
3
Hamburg
Frankfurt
Darmstadt
3
2
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
1550 Darmstadt
2
1205 Frankfurt
1411 Darmstadt
0800
Hamburg
Darmstadt
2
Paris
Tokyo
1
2
0100 Paris
2300 Tokyo
0800
Paris
Tokyo

Sample Output 

Scenario 1
Departure 0949 Hamburg
Arrival   1411 Darmstadt

Scenario 2
No connection

---

Miguel Revilla
2000-11-19

寫這題的時候，一開始以為可以使用 spfa 去跑，記錄最短的時間，次排序最晚的時間，
但這個想法是錯的，看看下面這個範例

for example. A-> B ->C
|----------------||---------------|
   |-------------------||--------|
  |------------------||---------|

在 B 如何決定？其實都有問題的，那如果記錄最晚時間，次排序最短時間，兩個 dp 交替得到？
不不不，這也是錯的。

安心點 dp 吧, dp[到達哪站][抵達的時間] = 最晚的出發時間。

這樣進行 dp 吧, dp[哪站][時間] = max(dp[][]);

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <map>
#include <queue>
using namespace std;
struct edge {
    int to;
    short startTime, endTime;
    edge(int a, short b, short c):
        to(a),startTime(b),endTime(c) {}
};
vector<edge> g[105];
short dist[2400][105];
void solve(char *name1, char *name2, int st, int ed, int st_time, int n) {
    int i, j, k;
    memset(dist, -1, sizeof(dist));
    for(i = 0; i < g[st].size(); i++) {
        if(g[st][i].startTime >= st_time) {
            dist[g[st][i].endTime][g[st][i].to] =
                max(dist[g[st][i].endTime][g[st][i].to], g[st][i].startTime);
        }
    }
    for(i = st_time; i < 2400; i++) {
        for(j = 0; j < n; j++) {
            if(dist[i][j] == -1)    continue;
            for(k = 0; k < g[j].size(); k++) {
                if(g[j][k].startTime >= i) {
                    dist[g[j][k].endTime][g[j][k].to] =
                        max(dist[g[j][k].endTime][g[j][k].to], dist[i][j]);
                }
            }
        }
        if(dist[i][ed] != -1) {
            printf("Departure %04d %s\n", dist[i][ed], name1);
            printf("Arrival   %04d %s\n", i, name2);
            return;
        }
    }
    puts("No connection");
}
int main() {
    int testcase, cases = 0;
    int N, T, M;
    int i, j, k;
    scanf("%d", &testcase);
    char cityName[1024], start[1024], end[1024];
    while(testcase--) {
        scanf("%d", &N);
        map<string, int> R;
        for(i = 0; i < N; i++) {
            scanf("%s", &cityName);
            R[cityName] = i;
            g[i].clear();
        }
        scanf("%d", &T);
        int x, y, ptime, time, startTime;
        while(T--) {
            scanf("%d", &M);
            for(i = 0; i < M; i++) {
                scanf("%d %s", &time, cityName);
                y = R[cityName];
                if(i && time >= ptime) {
                    g[x].push_back(edge(y, ptime, time));
                }
                x = y, ptime = time;
            }
        }
        scanf("%d %s %s", &startTime, start, end);
        x = R[start];
        y = R[end];
        printf("Scenario %d\n", ++cases);
        solve(start, end, x, y, startTime, N);
        puts("");
    }
    return 0;
}
/*
why use dp not short path algorithm?
for example. A-> B ->C
|----------------||---------------|
   |-------------------||--------|
  |------------------||---------|
*/