constint N = 10000 + 10; int n; std::vector<int> next[N]; bool vis[N];
voidinit(){ memset(vis, false, sizeof(vis)); std::cin >> n; for (int i = 1; i <= n; i++) { int a, b; std::cin >> a >> b; next[a].push_back(b); // 无向图,存双边 next[b].push_back(a); }
}
voiddfs(int k){ int side = 0; for (int j : next[k]) { if (!vis[j]) side++; } if (side == 1 && !vis[k]) { vis[k] = true; dfs(next[k][0]); } }
voidwork(){ int remain = n; int tem_remain; do { tem_remain = remain; for (int i = 1; i <= n; i++) { int side = 0; for (int j : next[i]) { if (!vis[j]) side++; } if (side == 1 && !vis[i]) { vis[i] = true; tem_remain -= 1; dfs(next[i][0]); } } } while (tem_remain != remain); for (int i = 1; i <= n; i++) if (!vis[i]) std::cout << i << " "; }
std::queue<int> q; auto next = std::vector<std::vector<int>>(N); auto val = std::vector<std::vector<int>>(N); std::array<bool, N> vis; std::array<longlong, N> dis; int n, m, start = 1;
voidinput();
voidinit();
voidspfa(){ while (!q.empty()) { int tem = q.front(); q.pop(); for (int i = 0; i < next[tem].size(); i++) { if (dis[next[tem][i]] > dis[tem] + val[tem][i]) { dis[next[tem][i]] = dis[tem] + val[tem][i]; if (!vis[next[tem][i]]) { vis[next[tem][i]] = true; q.push(next[tem][i]); } } } } for (int i = 1; i <= n; i++) std::cout << dis[i] << std::endl; }
intmain(){ input(); init(); spfa(); return0; }
voidinput(){ std::cin >> n >> m; // n 个点, m条边 for (int i = 1; i <= m; i++) { int a, b, t; // a -> b 存在一条距离为 t 的边 std::cin >> a >> b >> t; next[a].push_back(b); val[a].push_back(t); } }