Дейкстра

Revision ru1, by pakaka191, 2023-03-17 19:40:04

include <bits/stdc++.h>

using namespace std;

int main() { int n, s, f; cin >> n >> s >> f; int g[n][n]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> g[i][j]; } } s--; f--; int m[n]; int r[n]; for(int i = 0; i < n; i++){ m[i] = 0; r[i] = 1e9; } r[s] = 0; while(1){ int v = -1; int e = 2e9; for(int i = 0; i < n; i++){ if(m[i] == 0 && r[i] < e){ e = r[i]; v = i; } } if(v == -1) break; for(int j = 0; j < n; j++){ if(g[v][j] != -1 && m[j] == 0 && r[v] + g[v][j] < r[j]){ r[j] = r[v] + g[v][j]; } } m[v] = 1; } if(r[f] == 1e9) cout << -1; else cout << r[f]; }

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian pakaka191 2023-03-17 19:40:04 897 Первая редакция (опубликовано)