Lollypop @ SJTU

查的好艰辛, 过了 ... 高兴 ~~~

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

const int MAXN = 1010, MAXT = 110, MAXL = 1000100, infinite = 1 << 30;

struct Tnode{
  bool mk;
  int x, y, dp;
} sta[MAXL];
int N, M, L, early, S, T;
string cityName[MAXN];
int l[MAXN], prev[MAXL];
int c[MAXN][MAXT], t[MAXN][MAXT], num[MAXN][MAXT];
map<string, int> hash;

void init()
{
  string st;
  hash.clear();
  for (int i = 0; i < N; ++i)
    cin >> cityName[i], hash[cityName[i]] = i;

  memset(l, 0, sizeof(l));
  cin >> L;
  for (int i = 0; i < L; ++i)
    {
      cin >> l[i];
      for (int j = 0; j < l[i]; ++j)
    {
      cin >> t[i][j] >> st;
      c[i][j] = hash[st];           
    }
    }

  cin >> early;
  cin >> st, S = hash[st];
  cin >> st, T = hash[st];
}

bool cmp(const Tnode & a, const Tnode & b)
{
  if (t[a.x][a.y] != t[b.x][b.y]) return t[a.x][a.y] < t[b.x][b.y];
  if (!a.y || !b.y) return a.y;
  return t[a.x][a.y - 1] < t[b.x][b.y - 1];
}

string space(int x)
{
  if (x >= 1000) return "";
  if (x >= 100) return "0";
  if (x >= 10) return "00";
  else return "000";
}

void prepare()
{
  M = 0;
  for (int i = 0; i < L; ++i)
    for (int j = 0; j < l[i]; ++j)
      sta[M].x = i, sta[M++].y = j;

  sort(sta, sta + M, cmp);
  for (int i = 0; i < M; ++i)
    num[sta[i].x][sta[i].y] = i;

  for (int i = 0; i < M; ++i)
    if (c[sta[i].x][sta[i].y] == S && t[sta[i].x][sta[i].y] >= early)
      sta[i].mk = 1, sta[i].dp = t[sta[i].x][sta[i].y];
    else sta[i].mk = 0, sta[i].dp = 0;
}

void find_prev()
{
  hash.clear();
  memset(prev, -1, sizeof(prev));
  for (int i = 0; i < M; ++i)
    {
      int city = c[sta[i].x][sta[i].y];
      if (hash.count(cityName[city])) prev[i] = hash[cityName[city]];
      hash[cityName[city]] = i;
    }
}

void solve()
{
  prepare();
  find_prev();

  for (int i = 0, j; i < M; ++i)
    {
      if (c[sta[i].x][sta[i].y] == S) continue;
      if (prev[i] >= 0 && sta[prev[i]].mk)
    sta[i].mk = 1, sta[i].dp = sta[prev[i]].dp;
      if (sta[i].y > 0)
    {
      j = num[sta[i].x][sta[i].y - 1];
      if (sta[j].mk)
        sta[i].mk = 1, sta[i].dp >?= sta[j].dp;
    }
    }

  int dep = 0, arr = infinite;
  for (int i = 0; i < M; ++i)
    if (c[sta[i].x][sta[i].y] == T && sta[i].mk)
      {
      if (t[sta[i].x][sta[i].y] < arr)
    arr = t[sta[i].x][sta[i].y], dep = sta[i].dp;
      else if (t[sta[i].x][sta[i].y] == arr)
    dep >?= sta[i].dp;
      }

  if (arr == infinite) cout << "No connection" << endl;
  else cout << "Departure " << space(dep) << dep << ' ' << cityName[S] << endl << "Arrival   " << space(arr) << arr << ' ' << cityName[T] << endl;
}

int main()
{
  int data = 0;
  while (cin >> N && N)
    {
      if (data++) printf("\n");
      cout << "Scenario #" << data << endl;
      init();
      solve();
    }
}