一层bfs也T了,求助

UVA1599 Ideal Path

haluyaoac @ 2024-09-05 13:35:05

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

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

vector<arc> node[123456];
vector<int> clr[123456];
int n, dis[123456], path[123456], min_point;

void bfs() {
    queue<int> q,p;
    q.push(1);
    dis[1] = 0;
    int ok = 1;
    while (!q.empty()) {
        int f = q.front(); q.pop();
        if (!ok && dis[f] != dis[p.front()])break;
        for (int i = 0; i < node[f].size(); i++) {
            if (dis[node[f][i].v] != -1) {
                if (path[node[f][i].v] == f) {
                    if (clr[node[f][i].v].back() > node[f][i].c)clr[node[f][i].v].back() = node[f][i].c;
                }
                continue;
            }
            if (node[f][i].v == n) {
                clr[f].push_back(node[f][i].c);
                p.push(f);
                ok = 0;
            }
            if (ok) {
                clr[node[f][i].v] = clr[f];
                clr[node[f][i].v].push_back(node[f][i].c);
                dis[node[f][i].v] = dis[f] + 1;
                path[node[f][i].v] = f;
                q.push(node[f][i].v);
            }
        }
    }
    min_point = p.front(); p.pop();
    while (!p.empty()) {
        int ff = p.front(); p.pop();
        for (int i = 0; i <= dis[ff]; i++) {
            if (clr[ff][i] > clr[min_point][i]) { break; }
            if (clr[ff][i] < clr[min_point][i]) { min_point = ff; break; }
        }
    }
}
int main() {
    int m;
    while (cin >> n >> m) {
        memset(dis, -1, sizeof(dis));
        memset(path, 0, sizeof(path));
        while (m--) {
            int a, b, c;
            cin >> a >> b >> c;
            node[a].push_back(arc(b, c));
            node[b].push_back(arc(a, c));
        }
        bfs();
        for (int i = 1; i <= n;i++) {
            node[i].clear();
        }
        cout << dis[min_point] + 1 << endl;
        for (int i = 0; i < dis[min_point]; i++) {
            cout << clr[min_point][i] << ' ';
        }
        cout << clr[min_point][dis[min_point]] << endl;
        for (int i = 1; i <= n; i++) {
            clr[i].clear();
        }
    }
    return 0;
}

我换了个方法,我就用一次bfs,怎么又爆了,求助求助


|