题目

A市的地铁系统由C家公司运营，每家公司都开发了一些地铁线路，这些地铁线路连接了n个地铁站。

线路共有m条，每条双向边有三个属性 (u,v,c)代表这条线路连接u,v两站，由c公司运营。

地铁系统的收费规则为：每家公司都有单独的地铁票，售价为p，一张票允许你 "不间断" 地任意乘坐 这家公司的地铁线路，直到你到达终点或者换乘其他公司的线路。

也就是说：对于路径上相邻的边 (u,v,c1)和 (u,v,c2):若c1=c2则不花钱，否则需要花费p[c2]重 新买票，当然从起点上车时也要买票。

现在给定n和m条边，以及p数组，请你计算从起点1到所有点所需的最小花费。

输入格式:

第一行3个整数n,m,C

第二行c个正整数p[i]

接下来m行，每行3个正整数(u,v,c)代表一条双向边，保证u,v之间只有1条线路，保证u!=v

输出格式:

输出一行n个整数，代表从起点1出发到i=1...n的最小花费，特别地若不存在路径输出 -1 。

限制:

对于20%的数据：n,m,C<=5

对于40%的数据：n,m,C<=100

对于60%的数据：n<=100000,m<=2*100000,C<=100

对于100%的数据：1<=n<=10000,0<=m<=2*100000,1<=C<=1000000,0<p[i]<=1000000,1<=c<=C

代码：

// subway.cpp
#include <cstdio>
#include <queue>
using namespace std;

#define inf 0x3f3f3f3f
#define PII pair<int, int>
#define LL long long
#define N 1001023

int n, m, c, p[N], idx, f[N], to[N];
vector<PII> a[N]; // 每个公司的地铁线路列表
vector<PII> e[N << 1]; // 新图

void add(int u, int v, int w) {
    e[u].push_back({v, w});
    e[v].push_back({u, w});
}

LL d[N];
bool vis[N];
priority_queue<PII, vector<PII>, greater<>> q;

void dijkstra() {
    for (int i = 1; i <= idx; ++i)
        d[i] = inf;
    d[1] = 0;
    q.push({0, 1});

    while (!q.empty()) {
        int dist = q.top().first;
        int u = q.top().second;
        q.pop();
        if (vis[u] || dist >= d[u]) continue;
        vis[u] = 1;

        for (PII to : e[u]) {
            int v = to.first;
            LL w = to.second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
        }
    }
}

int get(int u) {
    if (u == f[u]) return u;
    return f[u] = get(f[u]);
}

int main() {
    // freopen("subway.in", "r", stdin);
    // freopen("subway.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &c);

    for (int i = 1; i <= c; ++i)
        scanf("%d", &p[i]);

    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        a[w].push_back({u, v});
    }

    idx = n;
    for (int i = 1; i <= c; ++i) {
        if (a[i].empty()) continue;

        for (PII edge : a[i]) {
            int u = edge.first;
            int v = edge.second;
            f[u] = u;
            f[v] = v;
            to[u] = to[v] = 0;
        }

        for (PII edge : a[i]) {
            int t1 = get(edge.first);
            int t2 = get(edge.second);
            /*if (t1 != t2)*/ f[t2] = t1;
        }

        for (PII edge : a[i]) {
            int u = edge.first;
            int v = edge.second;
            int t1 = get(u);
            int t2 = get(v);
            if (!to[t1]) to[t1] = ++idx;
            if (!to[t2]) to[t2] = ++idx;
            add(u, to[t1], p[i]);
            add(v, to[t2], p[i]);
        }
    }

    dijkstra();
    
    for (int u = 1; u <= n; ++u) {
        if (d[u] == inf) printf("-1 ");
        else printf("%lld ", d[u] / 2);
    }
    
    puts("");
    return 0;
}

修改代码