Advertisement
Guest User

Dijkstra 2.0

a guest
Dec 12th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int N, M, start, finish;
  9. int E[1000][1000];
  10. bool used[1000];
  11. int dist[1000];
  12.  
  13. void dijkstra(int count) {
  14.     if (count == 0)
  15.         return;
  16.  
  17.     int min_dist = 999999999;
  18.     int min_vertex;
  19.     for (int i = 1; i <= N; i++) {
  20.         if (used[i] == false && dist[i] < min_dist) {
  21.             min_dist = dist[i];
  22.             min_vertex = i;
  23.         }
  24.     }
  25.  
  26.     used[min_vertex] = true;
  27.  
  28.     for (int to = 1; to <= N; to++) {
  29.         int len = E[min_vertex][to];
  30.         if (len != -1) {
  31.             dist[to] = min(dist[to], dist[min_vertex] + len);
  32.         }
  33.     }
  34.     dijkstra(count - 1);
  35. }
  36.  
  37. int main() {
  38.     freopen("input.txt", "r", stdin);
  39.     freopen("output.txt", "w", stdout);
  40.     cin >> N >> start >> finish;
  41.  
  42.     for (int i = 1; i <= N; i++) {
  43.         for (int j = 1; j <= N; j++) {
  44.             int len;
  45.             cin >> len;
  46.             E[i][j] = len;
  47.         }
  48.     }
  49.  
  50.     for (int i = 1; i <= N; i++)
  51.         dist[i] = 999999999;
  52.  
  53.  
  54.     dist[start] = 0;
  55.  
  56.     dijkstra(N - 1);
  57.  
  58.     cout << dist[finish] << "\n";
  59.  
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement