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 rainbow_cat @ 2024-09-04 16:22:46
@haluyaoac 这……输入不会TLE么?
by YYZ_klee_KimDog @ 2024-09-04 16:23:31
wyy,jbl
by rainbow_cat @ 2024-09-04 16:26:26
@YANGYUZE1 ???
by haluyaoac @ 2024-09-04 16:27:44
@rainbow_cat 兄弟,怎么说,我快暴毙了
by YYZ_klee_KimDog @ 2024-09-04 16:28:29
@rainbow_cat 辱骂,已被我举报
by rainbow_cat @ 2024-09-04 16:29:55
@YANGYUZE1 兄弟,这是正经的求助帖啊
by haluyaoac @ 2024-09-04 16:29:58
@YANGYUZE1 ??咋了,现在改
by YYZ_klee_KimDog @ 2024-09-04 16:30:46
@haluyaoac
by rainbow_cat @ 2024-09-04 16:31:07
@haluyaoac ios::sync_with_stdio(0)
by haluyaoac @ 2024-09-04 16:31:45
@YANGYUZE1 呜呜呜,真的会哭