Advertisement
Mirbek

Расстояние между вершинами

Jan 11th, 2022
553
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. using namespace std;
  2.  
  3. const int N = 2e5 + 5;
  4. const int inf = 2e9;
  5.  
  6. int n, m, s, t;
  7. long long dist[N];
  8. vector < pair <int, int> > g[N];
  9.  
  10. int main(){
  11.  
  12.     for (int i = 0; i < N; i++) {
  13.         dist[i] = inf;
  14.     }
  15.  
  16.     cin >> n >> m >> s >> t;
  17.  
  18.     for (int i = 1; i <= m; i++) {
  19.         int u, v, len;
  20.         cin >> u >> v >> len;
  21.         g[u].push_back(make_pair(v, len));
  22.         g[v].push_back(make_pair(u, len));
  23.     }
  24.  
  25.     set < pair <int, int> > st;
  26.     dist[s] = 0;
  27.     st.insert({dist[s], s});
  28.  
  29.     while (!st.empty()) {
  30.         int v = st.begin()->second;
  31.         st.erase(st.begin());
  32.  
  33.         for (int i = 0; i < g[v].size(); i++) {
  34.             int to = g[v][i].first, len = g[v][i].second;
  35.             if (dist[v] + len < dist[to]) {
  36.                 st.erase({dist[to], to});
  37.                 dist[to] = dist[v] + len;
  38.                 st.insert({dist[to], to});
  39.             }
  40.         }
  41.     }
  42.  
  43.     if (dist[t] == inf) {
  44.         cout << -1 << endl;
  45.     } else {
  46.         cout << dist[t] << endl;
  47.     }
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement