Solution

交汇地铁类型的图，一般都考虑分层建图或者借助额外的点建图。我们把起始的站点用 $hash$ 表保留编号，上下地铁的位置建立额外的编号，这样就可以保证我们每次上下地铁计算到正确的票价。

所以我们再把地铁路线上的点拆分成向左向右两边的点，那么很明显边权存在两个(票价，时间)，那么从起始站点上地铁我们开销就是 $(1,0)$ ，从地铁下来开销 $(0,0)$ ，同一个地铁上的不同站点，注意这里不能连接到了起始站点，这和地铁路线上的站点已经被我们分隔开来了，这些开销是 $(0,1)$ 。

那么从 $s\to t$ 的最小票价，就是通过第一权值求解最短路，使用 $dijkstra$ 算法。

从 $s\to t$ 的最大时间就是把最短路图中的边挑选出来，最短路图的概念就是在求解单源最短路之后 $dis[u]+w==dis[v]$ 的边 $<u,v,w>$ ，根据最短路图的性质很明显可以发现这一定是一个有向无环图，通过最短路图求解拓扑排序就可以找到去 $t$ 的最长边。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
#define debug(x) cout << #x << ":" << x << '\n'
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 2e6 + 7;
const int M = 3e6 + 7;

struct Node {
    //int u;
    int v, next;
    int cost, time;
};
struct Map {
    int head[N], tot = 0;
    Node edge[M << 1];
    void init() { ms(head, -1); tot = 0; }
    void add(int u, int v, int cost, int time) {
        tot++;
        edge[tot].v = v;
        edge[tot].next = head[u];
        edge[tot].cost = cost;
        edge[tot].time = time;
        head[u] = tot;
    }
}G1, G2;
int n, m;/*改数组大小！！*/
unordered_map<string, int> mp;
priority_queue<pai, vector<pai>, greater<pai>> pq;
int dis[N], du[N];
bool vis[N];

void dijkstra(int s) {
    ms(dis, 0x3f);
    pq.push({ 0,s });
    dis[s] = 0;
    while (pq.size()) {
        int u = pq.top().second; pq.pop();
        if (vis[u])    continue;
        vis[u] = 1;
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v, cost = G1.edge[i].cost;
            if (dis[v] > dis[u] + cost) {
                dis[v] = dis[u] + cost;
                pq.push({ dis[v],v });
            }
        }
    }
}

void solve() {
    js;
    G1.init(); G2.init();
    cin >> m >> n;

    string name;
    rep(i, 1, n) {
        cin >> name;
        mp[name] = i;
    }
    int cnt = n, x, id;

    rep(i, 1, m) {
        cin >> x;
        rep(j, 1, x) {
            cin >> name;
            id = mp[name];
            G1.add(id, cnt + j, 1, 0);
            G1.add(cnt + j, id, 0, 0);
            G1.add(id, cnt + j + x, 1, 0);
            G1.add(cnt + j + x, id, 0, 0);
        }
        rep(i, 1, x - 1) G1.add(cnt + i, cnt + i + 1, 0, 1);
        rep(i, 0, x - 2)    G1.add(cnt + 2 * x - i, cnt + 2 * x - 1 - i, 0, 1);
        cnt += 2 * x;
    }
    int s, t;
    cin >> name; s = mp[name];
    cin >> name; t = mp[name];

    dijkstra(s);
    if (dis[t] == INF) {
        cout << -1 << endl << 0 << endl;
        return;
    }
    cout << dis[t] << endl;

    rep(u, 1, cnt) {
        for (int i = G1.head[u]; ~i; i = G1.edge[i].next) {
            int v = G1.edge[i].v, cost = G1.edge[i].cost, time = G1.edge[i].time;
            if (dis[u] + cost == dis[v]) {
                G2.add(u, v, cost, time);
                ++du[v];
            }
        }
    }
    ms(dis, -0x3f);
    dis[s] = 0;
    queue<int> q;
    rep(i, 1, cnt)    if (!du[i])    q.push(i);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = G2.head[u]; ~i; i = G2.edge[i].next) {
            int v = G2.edge[i].v, time = G2.edge[i].time;
            if (--du[v] == 0)    q.push(v);
            dis[v] = max(dis[v], dis[u] + time);
        }
    }
    cout << dis[t] << endl;
}

int main() {
    //int T = read();    rep(_, 1, T)
    {
        solve();
    }
    return 0;
}

题解 | #[JSOI2015]地铁线路#

Solution