t了,我号emo,求帮助

UVA1599 Ideal Path

haluyaoac @ 2024-09-04 16:19:09

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

typedef struct list {
    int v, c;
    list(int v, int c) :v(v), c(c) {}
}list;

vector<list> node[100005];
int n, dis[100005], clrr[100005], path[100005][2], num = 0;;

void bfsn() {
    queue<int> q;
    q.push(n);
    dis[n] = 0;
    while (!q.empty()) {
        int f = q.front(); q.pop();
        for (int i = 0; i < node[f].size(); i++) {
            if (dis[node[f][i].v] != -1)continue;
            dis[node[f][i].v] = dis[f] + 1;
            q.push(node[f][i].v);
        }
    }
}

void bfs1() {
    queue<int> q;
    q.push(1);
    path[1][0] = 0;
    while (!q.empty()) {
        queue<int> p = q;
        while (!q.empty()) {
            int f = q.front(); q.pop();
            for (int i = 0; i < node[f].size(); i++) {
                if (dis[node[f][i].v] != dis[f] - 1)continue;
                if (node[f][i].c < clrr[dis[node[f][i].v]])clrr[dis[node[f][i].v]] = node[f][i].c;
            }
        }
        while (!p.empty()) {
            int f = p.front(); p.pop();
            for (int i = 0; i < node[f].size(); i++) {
                if (dis[node[f][i].v] != dis[f] - 1)continue;
                if (node[f][i].c == clrr[dis[node[f][i].v]]) {
                    q.push(node[f][i].v);
                    path[node[f][i].v][0] = f;
                    path[node[f][i].v][1] = clrr[dis[node[f][i].v]];
                }
            }
        }
    }
}

int main() {
    int m;
    while (cin >> n >> m) {
        int mm = m;
        memset(dis, -1, sizeof(dis));
        memset(path, 0, sizeof(path));
        while (mm--) {
            int u, v, c;
            cin >> u >> v >> c;
            node[u].push_back(list(v, c));
            node[v].push_back(list(u, c));
        }
        bfsn();
        for (int i = 0; i < dis[1]; i++) {
            clrr[i] = 1000000000;
        }
        cout << dis[1] << endl;
        bfs1();
        for (int i = 1; i <= n; i++) {
            node[i].clear();
        }
        for (int i = dis[1] - 1; i > 0; i--) {
            cout << clrr[i] << ' ';
        }
        cout << clrr[0] << endl;
    }
    return 0;
}

有没有什么优化的机会啊兄弟们


by haluyaoac @ 2024-09-04 16:33:21

@rainbow_cat 我用scanf是不是也可以?


by haluyaoac @ 2024-09-04 16:37:45

@rainbow_cat 改了还是t,哭死我了


上一页 |