「JSOI2015」地铁线路

传送门

第一问很简单：对于每条线路建一个点，然后所有该条线路覆盖的点向它连边，权值为 (1) ，然后它向所有线路上的点连边，权值为 (0) 。

然后，跑一边最短路就可以求出第一问了。

接下来考虑第二问。

我们在最短路图上面跑 ( ext{DP}) 我们把所有线路按照 (dis) 排序，然后用距离为 (dis - 1) 的线路来更新。

我们发现如果一条最短路为 (d) 的线路上出现了一个最短路为 (d) 的点，那么显然我们不会在这里上车，可能在这里下车。

暴力的搞法就是暴力枚举，每次 (O(n^2)) 的转移：(dp_i leftarrow dp_j + dis(i, j),dis_i = dis_j + 1)

但我们发现一条线路是一条链，所以我们只需要每次记一下前缀和后缀的最大值然后再择优，这样就可以 (O(n)) 转移了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <deque>
#include <map>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template < class T > inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
    s = f ? -s : s;
}
 
const int _ = 5e5 + 5, __ = 2e6 + 5;
 
int tot, head[_]; struct Edge { int v, w, nxt; } edge[__ << 1];
inline void Add_edge(int u, int v, int w) { edge[++tot] = (Edge) { v, w, head[u] }, head[u] = tot; }
 
int n, m, s, t, node, dis[_], dp[_], p[_], pre[_], suf[_];
inline bool cmp(const int& i, const int& j) { return dis[i + n] < dis[j + n]; }
string str;
vector < int > vec[_];
map < string, int > mp;
deque < int > Q;
inline void Dijkstra() {
    memset(dis, -1, sizeof dis), dis[s] = 0;
    Q.push_back(s);
    while (!Q.empty()) {
    	int u = Q.front(); Q.pop_front();
    	for (rg int i = head[u]; i; i = edge[i].nxt) {
	        int v = edge[i].v, w = edge[i].w;
	        if (~dis[v]) continue ;
	        if (w) dis[v] = dis[u] + w, Q.push_back(v);
	        else dis[v] = dis[u], Q.push_front(v);
	    }
    }
}
 
inline void calc() {
    for (rg int i = 1; i <= m; ++i) p[i] = i;
    sort(p + 1, p + m + 1, cmp);
    int l, r = 0;
    while (r < m && dis[p[r + 1] + n] <= 0) ++r;
    for (rg int d = 1; d <= m; ++d) {
    	l = r + 1;
    	while (r < m && dis[p[r + 1] + n] == d) ++r;
    	for (rg int j = l; j <= r; ++j) {
	        int u = p[j], len = vec[u].size() - 1;
	        for (rg int k = 0; k <= len + 1; ++k) pre[k] = suf[k] = -2e9;
	        for (rg int k = 1; k <= len; ++k) {
		        int v = vec[u][k];
		        if (dis[v] == d - 1) pre[k] = suf[k] = dp[v];
	        }
	        for (rg int k = 1; k <= len; ++k) pre[k] = max(pre[k], pre[k - 1] + 1);
	        for (rg int k = len; k >= 1; --k) suf[k] = max(suf[k], suf[k + 1] + 1);
	        for (rg int k = 1; k <= len; ++k) {
		        int v = vec[u][k];
		        if (dis[v] == d) dp[v] = max(dp[v], max(pre[k], suf[k]));
	        }
	    }
    }
}
 
int main() {
#ifndef ONLINE_JUDGE
    file("cpp");
#endif
    read(m), read(n);
    for (rg int i = 1; i <= n; ++i) cin >> str, mp[str] = ++node;
    for (rg int x, i = 1; i <= m; ++i) {
    	read(x), vec[i].push_back(0);
    	while (x--) {
	        cin >> str, vec[i].push_back(mp[str]);
	        Add_edge(mp[str], i + n, 1), Add_edge(i + n, mp[str], 0);
	    }
    }
    cin >> str, s = mp[str];
    cin >> str, t = mp[str];
    Dijkstra(), calc();
    printf("%d
%d
", dis[t], dp[t]);
    return 0;
}