求大神帮助

题目总版

linhanmo @ 2024-11-19 18:30:33

能不能帮个忙，C++?

【题目描述】

翠江城是一个交通发展的城市，城里的地铁四通八达。地铁一共有 n个站点，m条线路，每条线路连接两个站点，可以在这两个站点之间双向通行。特殊的是，翠江城的地铁由多家公司运营，乘坐每家公司的地铁都需要 1 元钱，但换乘同一家公司的地铁不需要再次付费。小 D 想从 1 号站点前往 n 号站点，他想知道最小费用是多少。【输入格式】

输入第一行有两个正整数 n,m 表示站点数和线路数。接下来 m 行，每行三个整数 pi,qi,ci，表示这条线路连接的两个站点以及运营它的公司编号。【输出格式】

输出仅包括一行一个整数，表示答案。如果无法到达，输出 -1。

样例输入

8 11

1 3 1

1 4 2

2 3 1

2 5 1

3 4 3

3 6 3

3 7 3

4 8 4

5 6 1

6 7 5

7 8 5

样例输出

样例解释

先乘坐公司 1 的地铁 1→3→2→5→6，然后乘坐公司 5 的地铁 6→7→8。

【数据范围】

对于30% 的数据，满足n≤1000，m≤2000。

对于另外20% 的数据，满足 ci≤4。

对于 100%的数据，满足2≤n≤10^5，1≤m≤2×10 ^5 ，1≤ci≤10^6 ，pi!=qi.

by linhanmo @ 2024-11-19 18:55:39

原代码60分

#include <bits/stdc++.h>
using namespace std;
inline unsigned read(unsigned &x) {
    x = 0;
    char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
vector<pair<int,int> > g[100005];
queue<pair<int, int> > q;
unsigned n, m, mc = INT_MAX, c[200005][101];
int main() {
    read(n), read(m);
    memset(c,0x3f,sizeof(c));
    for (unsigned i = 0, p, q, c; i < m; ++i) read(p), read(q), read(c), g[p].push_back({q, c}), g[q].push_back({p, c});
    q.push({1, -1}), c[1][0] = 0;
    while (!q.empty()) {
        auto [cr, second] = q.front();
        q.pop();
        for (const auto & ed : g[cr]) {
            unsigned i = ed.first, c_ = ed.second, _c;
            _c = c[cr][second == -1 ? 0 : second];
            if (c_ != second) ++_c;
            if (_c < c[i][c_]) c[i][c_] = _c, q.push({i, c_});
        }
    }
    for (unsigned i = 0; i < 101; ++i) mc = min(mc, c[n][i]);
    if (mc == 1061109567) printf("-1");
    else printf("%d", mc);
    return 0;
}

by linhanmo @ 2024-11-19 18:58:39

1 Accepted10 87ms 85.8 MiB

2 Wrong Answer0 43ms 79.8 MiB

3 Accepted10 108ms 87.5 MiB

4 Wrong Answer0 184ms 84.3 MiB

5 Wrong Answer0 43ms 80.1 MiB

6 Accepted10 74ms 85.2 MiB

7 Accepted10 133ms 84.3 MiB

8 Wrong Answer0 43ms 79.9 MiB

9 Accepted10 146ms 87.1 MiB

10 Accepted10 145ms 87.6 MiB