1808: 地铁

Link

Solution

拆点+最短路

Code

#include <algorithm>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define INT_MAX 0x3f3f3f3f
#define mpr make_pair
const int maxn = 200000 + 10;
using namespace std;

int n, m, idx = 0;
int dis[maxn], vis[maxn];
vector<pair<int, int>>G[maxn];
map<pair<int, int>, int>mp;
vector<int>stas[maxn];

int get(int v, int c) {
    int &res = mp[{v, c}];
    if (!res)res = ++idx;
    return res;
}

int dijk() {
    int st = get(1, stas[1][0]), ed = get(n, stas[n][0]);
    memset(dis, INT_MAX, sizeof(dis));
    dis[st] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
    q.push({ 0,st });
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (!vis[u]) {
            vis[u] = 1;
            for (vector<pair<int, int>>::iterator i = G[u].begin(); i != G[u].end(); i++) {
                int v = (*i).first, c = (*i).second;
                if (dis[v] > dis[u] + c) {
                    dis[v] = dis[u] + c;
                    q.push({ dis[v],v });
                }
            }
        }
    }
    return dis[ed];
}

int main() {
    int a, b, c, t;
    while (cin >> n >> m) {
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> c >> t;
            stas[a].push_back(c), stas[b].push_back(c);
            a = get(a, c), b = get(b, c);
            G[a].push_back({ b,t });
            G[b].push_back({ a,t });
        }
        for (int i = 1; i <= n; i++) {
            sort(stas[i].begin(), stas[i].end());
            stas[i].erase(unique(stas[i].begin(), stas[i].end()), stas[i].end());
            for (int j = 1; j < stas[i].size(); j++) {
                int u = get(i, stas[i][j - 1]), v = get(i, stas[i][j]), c = stas[i][j] - stas[i][j - 1];
                if (i == 1 || i == n)c = 0;
                G[u].push_back({ v, c });
                G[v].push_back({ u, c });
            }
        }
        cout << dijk() << endl;
        for (int i = 0; i <= n; i++) { G[i].clear(), stas[i].clear(); }
        memset(vis, 0, sizeof(vis));
        mp.clear();
    }
    return 0;
}