typedef long long ll; #include using namespace std; template void Fill(A (&array)[N], const T &val){ std::fill( (T*)array, (T*)(array+N), val ); } typedef pair P; struct edge { ll to; ll cost; }; vector G[100010]; int main() { ll n,m; std::cin >> n>>m; ll d[100010]; ll inf = 100000000000000+10; Fill(d,inf); d[0] = 0; for (int i = 0; i < m; i++) { ll tmp_a,tmp_b,tmp_c; std::cin >> tmp_a>>tmp_b>>tmp_c; tmp_a--; tmp_b--; edge e1 = {tmp_b,tmp_c}; edge e2 = {tmp_a,tmp_c}; G[tmp_a].push_back(e1); G[tmp_b].push_back(e2); } priority_queue, greater

> que; que.push(P(0, 0)); ll logest[100010]; Fill(logest,0); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first) continue; for (int i=0; i d[v] + e.cost) { d[e.to] = d[v] + e.cost; // logest[e.to] = max({logest[e.to],logest[v],e.cost}); // std::cout << logest[e.to] << std::endl; que.push(P(d[e.to], e.to)); } } } // 最大距離消えるバージョン ll d2[100010]; Fill(d2,inf); d2[0] = 0; priority_queue, greater

> que2; que2.push(P(0,0)); while (!que2.empty()) { P p = que2.top(); que2.pop(); int v = p.second; if (d2[v] < p.first) continue; for (int i=0; i d2[v] + e.cost - now_longest + logest[v]) { d2[e.to] = d2[v] + e.cost - now_longest + logest[v]; logest[e.to] = max({logest[e.to],now_longest}); // std::cout << logest[e.to] << std::endl; que2.push(P(d2[e.to], e.to)); } } } for (int i = 0; i < n; i++) { std::cout << d[i]+d2[i]<< std::endl; } }