# дейкстра

unknown
c_cpp
2 years ago
1.6 kB
2
Indexable
Never
```#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

mt19937 rnd(time(0));

#define ioss ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("sum.in", "r", stdin); freopen("sum.out", "w", stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

template<class T>
ll upmax(T &a, T b) { return (b > a) ? a = b, 1 : 0; }

template<class T>
ll upmin(T &a, T b) { return (b < a) ? a = b, 1 : 0; }

const ll inf = 1e18 + 7;

void solve(){
int n, m;
cin >> n >> m;
vector<vector<pair<ll, ll>>> graph(n, vector<pair<ll,ll>> ());
for(int i = 0; i < m; i += 1){
ll x, y, w;
cin >> x >> y >> w;
x--,y--;
graph[x].pb({y, w});
graph[y].pb({x, w});
}
vector<ll> dist(n, inf);
set<pair<ll,ll>> st;
st.insert({0, 0});
dist[0] = 0;
while(!st.empty()) {
auto v = *st.begin();
st.erase(v);
for (auto [to, w]: graph[v.second]) {
if (dist[to] > dist[v.second] + w) {
st.erase({dist[to], to});
dist[to] = dist[v.second] + w;
st.insert({dist[to], to});
}
}
}
for(auto i : dist){
cout << i << ' ';
}
cout << '\n';
}

signed main() {
// ioss
// file
// (a += b) -> return value
int t = 1;
// cin >> t;
while (t--) {
solve();
}
// printf("Time taken: %.10fs\n", (double)(clock() - CLOCK_START)/CLOCKS_PER_SEC);
return 0;
}```