「JSOI2015」地铁线路

「JSOI2015」地铁线路

传送门

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

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

接下来考虑第二问。

我们在最短路图上面跑 \(\text{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\n%d\n", dis[t], dp[t]);

    return 0;

}