题目分析

我们经营一个由 $n$ 个城市（编号 $1$ 至 $n$）组成的铁路系统，其中列车严格按照时刻表运行，且均为直达列车。乘客可以通过换乘（换乘时间为 $0$）从城市 $p$ 前往城市 $q$，但必须满足后一趟列车的发车时间不早于前一趟列车的到站时间。

最优连接定义为：不存在其他从 $p$ 出发时间不晚于 $A$ 且到达 $q$ 时间不早于 $B$ 的路线。仅考虑当日可达的路线。

#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
	char s[10], e[10];
	int nxt;
};

int n, m;
vector<node> nodeData[100001]; // 修改变量名避免冲突
vector<int> l[100001];
int s[100001];
int g[1000005], nxt[2000005], v[2000005], co = 0, dp[1000005];

int change(char *ori)
{
	char tmp[10];
	strcpy(tmp, ori);
	return atoi(strtok(tmp, ":")) * 60 + atoi(strtok(NULL, ":"));
}

void addedge(int s, int e)
{
	v[co] = e;
	nxt[co] = g[s];
	g[s] = co++;
}

int solve(int pos)
{
	if (dp[pos] != -1)
		return dp[pos];
	else if (g[pos] == -1 && pos >= s[n - 1])
		return dp[pos] = l[n][pos - s[n - 1]];
	else
	{
		dp[pos] = (pos >= s[n - 1] ? l[n][pos - s[n - 1]] : 0xfffffff);
		for (int p = g[pos]; p != -1; p = nxt[p])
			dp[pos] = min(dp[pos], solve(v[p]));
		return dp[pos];
	}
}

void print(int time)
{
	printf("%02d:%02d", time / 60, time % 60);
}

int main()
{
	scanf("%d", &n);
	s[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &m);
		while (m--)
		{
			node tmp;
			scanf("%s%s%d", tmp.s, tmp.e, &tmp.nxt);
			nodeData[i].push_back(tmp); // 同步修改此处
			l[i].push_back(change(tmp.s));
			if (tmp.nxt == n)
				l[n].push_back(change(tmp.e));
		}
		sort(l[i].begin(), l[i].end());
		vector<int>::iterator end = unique(l[i].begin(), l[i].end());
		while (l[i].end() != end)
			l[i].pop_back();
		s[i] = s[i - 1] + l[i].size();
	}
	memset(g, -1, sizeof(g));
	memset(dp, -1, sizeof(dp));
	co = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = s[i - 1]; j < s[i] - 1; j++)
			addedge(j, j + 1);
		for (int j = 0; j < nodeData[i].size(); j++) // 此处也需修改
			if (lower_bound(l[nodeData[i][j].nxt].begin(), l[nodeData[i][j].nxt].end(), change(nodeData[i][j].e)) != l[nodeData[i][j].nxt].end())
				addedge(s[i - 1] + lower_bound(l[i].begin(), l[i].end(), change(nodeData[i][j].s)) - l[i].begin(),
					s[nodeData[i][j].nxt - 1] + lower_bound(l[nodeData[i][j].nxt].begin(), l[nodeData[i][j].nxt].end(), change(nodeData[i][j].e)) - l[nodeData[i][j].nxt].begin());
	}
	vector<pair<int, int>> ans;
	for (int i = s[1] - 1; i >= 0; i--)
		if (solve(i) != 0xfffffff && (ans.empty() || solve(i) < ans.back().second))
			ans.push_back(make_pair(l[1][i], solve(i)));
	printf("%d\n", ans.size());
	for (int i = ans.size() - 1; i >= 0; i--)
	{
		print(ans[i].first);
		printf(" ");
		print(ans[i].second);
		printf("\n");
	}
	return 0;
}