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,怎么又爆了,求助求助