csu1808

csu1808

题意

n 个点间有 m 条地铁，每条地铁可能属于不同的线路，每条地铁有权值即通过时花费的时间，如果乘坐第 i 条地铁来到地铁站 s，再乘坐第 j 条地铁离开，需要花费额外的时间 \(|c[i] - c[j]|\) 即地铁线路之差。

分析

点本身不具有线路信息，如果直接对点做最短路，无法判断要更新的点是来自于哪个线路。

而边具有唯一的线路信息，可以直接把边当成点，使用链式前向星来构造图，对边做最短路。

code

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long ll;

typedef pair<ll, int> P;

const ll INF = 1e15;

const int MAXN = 2e5 + 10;

int head[MAXN];

int cnt;

struct Edge {

    int next, to, stp;

    ll w;

}edge[MAXN];

void add(int u, int v, int stp, ll w) {

    edge[cnt].w = w;

    edge[cnt].to = v;

    edge[cnt].stp = stp;

    edge[cnt].next = head[u];

    head[u] = cnt++;

}

int n, m;

vector<Edge> g[MAXN];

ll d[MAXN];

ll ans;

int vis[MAXN];

void dijkstra() {

    ans = INF;

    priority_queue<P, vector<P>, greater<P> > que;

    memset(vis, 0, sizeof vis);

    for(int i = 0; i <= cnt; i++) d[i] = INF;

    for(int i = head[1]; ~i; i = edge[i].next) {

        d[i] = edge[i].w;

        que.push(P(edge[i].w, i));

    }

    while(!que.empty()) {

        P p = que.top();

        que.pop();

        int u = p.second;

        vis[u] = 1;

        if(edge[u].to == n) {

            ans = min(ans, d[u]);

        }

        for(int i = head[edge[u].to]; ~i; i = edge[i].next) {

            if(!vis[i] && d[i] > d[u] + edge[i].w + abs(edge[i].stp - edge[u].stp)) {

                d[i] = d[u] + edge[i].w + abs(edge[i].stp - edge[u].stp);

                que.push(P(d[i], i));

            }

        }

    }

}

int main() {

    while(~scanf("%d%d", &n, &m)) {

        memset(head, -1, sizeof head);

        cnt = 0;

        for(int i = 0; i < m; i++) {

            int x, y, z;

            ll k;

            scanf("%d%d%d%lld", &x, &y, &z, &k);

            add(x, y, z, k);

            add(y, x, z, k);

        }

        dijkstra();

        printf("%lld\n", ans);

    }

    return 0;

}