1c:I[83391,["/_next/static/chunks/01ctw1akxhipf.js","/_next/static/chunks/0es-u.8d.mnrl.js","/_next/static/chunks/0dy1a2.mvnkkn.js","/_next/static/chunks/1490m.ueos6wm.js","/_next/static/chunks/0e0r8s6q6rqo3.js","/_next/static/chunks/06ql-volcxfrm.js"],"ProblemWorkspace",1] 1f:I[27201,["/_next/static/chunks/01xlw8hd842-c.js","/_next/static/chunks/0-mla.nmfqw.d.js"],"IconMark"] 1d:T407,#include using namespace std; const long long MOD = 1000000007; int main() { int n, m; cin >> n >> m; vector>> adj(n + 1); for (int i = 0; i < m; i++) { int x, y; long long c; cin >> x >> y >> c; adj[x].push_back({y, c}); adj[y].push_back({x, c}); } int s; cin >> s; vector dist(n + 1, -1), cnt(n + 1, 0); priority_queue, vector>, greater<>> pq; dist[s] = 0; cnt[s] = 1; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] != -1 && d > dist[u]) continue; for (auto& [v, w] : adj[u]) { long long nd = d + w; if (dist[v] == -1 || nd < dist[v]) { dist[v] = nd; cnt[v] = cnt[u]; pq.push({nd, v}); } else if (nd == dist[v]) { cnt[v] = (cnt[v] + cnt[u]) % MOD; } } } for (int i = 1; i <= n; i++) cout << (dist[i] == -1 ? 0 : cnt[i]) << (i < n ? " " : "\n"); return 0; } 1e:T407,#include using namespace std; const long long MOD = 1000000007; int main() { int n, m; cin >> n >> m; vector>> adj(n + 1); for (int i = 0; i < m; i++) { int x, y; long long c; cin >> x >> y >> c; adj[x].push_back({y, c}); adj[y].push_back({x, c}); } int s; cin >> s; vector dist(n + 1, -1), cnt(n + 1, 0); priority_queue, vector>, greater<>> pq; dist[s] = 0; cnt[s] = 1; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] != -1 && d > dist[u]) continue; for (auto& [v, w] : adj[u]) { long long nd = d + w; if (dist[v] == -1 || nd < dist[v]) { dist[v] = nd; cnt[v] = cnt[u]; pq.push({nd, v}); } else if (nd == dist[v]) { cnt[v] = (cnt[v] + cnt[u]) % MOD; } } } for (int i = 1; i <= n; i++) cout << (dist[i] == -1 ? 0 : cnt[i]) << (i < n ? " " : "\n"); return 0; }