而边权最大只有 \(50\) , \(50\) 次入队足够让 \(ans\) 由所有的边权更新一遍了
AC_Code #include<bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; const int N = 2e5 + 10; struct node{ int dis , pos; bool operator <( const node &x )const{ return x.dis < dis; } }; struct Edge{ int to , w , nex; }edge[N << 1]; int head[N], dis[51][N] , tot , vis[N] , n , m , s , ans[N]; inline void add_edge(int u , int v , int d) { edge[++ tot].w = d; edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot; } inline void dijkstra(int s) { for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= 50 ; j ++) ans[i] = dis[j][i] = inf; ans[s] = 0; priority_queue <node> que; que.push(node{0 , s}); while(!que.empty()) { node tmp = que.top(); que.pop(); int u = tmp.pos , d = tmp.dis ; if(vis[u] > 50) continue; vis[u] ++; for(int i = head[u] ; i ; i = edge[i].nex) { int v = edge[i].to , w = edge[i].w; for(int j = 1 ; j <= 50 ; j ++) { int cost = dis[j][u] + (j + w) * (j + w); if(cost < ans[v]) { ans[v] = cost; if(vis[v] <= 50) que.push(node{ans[v] , v}); } } if(dis[w][v] > ans[u]) { dis[w][v] = ans[u]; if(vis[v] <= 50) que.push(node{dis[w][v] , v}); } } } } signed main() { cin >> n >> m; for(int i = 1 ; i <= m ; i ++) { int u , v , w; cin >> u >> v >> w; add_edge(u , v , w); add_edge(v , u , w); } dijkstra(1); for(int i = 1 ; i <= n ; i ++) { if(ans[i] == inf) ans[i] = -1; cout << ans[i] << " "; } return 0; }