Okorosso

fast Dijkstra 16/19

Jun 4th, 2021 (edited)
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3.  
  4. int intMax = 4000;
  5. using namespace std;
  6.  
  7. vector<int> dijkstra(int n, int startPoint, vector<vector<int>> &w) {
  8.     vector<bool> visited(n);
  9.     vector<int> distance(n);
  10.     for (int i = 0; i < n; i++) {
  11.         distance[i] = w[startPoint][i];
  12.         visited[i] = false;
  13.     }
  14.     distance[startPoint] = 0;
  15.     int index = 0, u;
  16.     for (int i = 0; i < n; i++) {
  17.         int minDistance = intMax;
  18.         for (int j = 0; j < n; j++) {
  19.             if (!visited[j] and distance[j] != -1 and distance[j] < minDistance) {
  20.                 minDistance = distance[j];
  21.                 index = j;
  22.             }
  23.         }
  24.         u = index;
  25.         visited[u] = true;
  26.         for (int j = 0; j < n; j++) {
  27.             if (!visited[j] and w[u][j] != -1 and distance[u] != -1 and (distance[u] + w[u][j] < distance[j])) {
  28.                 distance[j] = distance[u] + w[u][j];
  29.             }
  30.         }
  31.     }
  32.  
  33.     return distance;
  34. }
  35.  
  36. int main() {
  37.     ifstream fin("input.txt");
  38.     ofstream fout("output.txt");
  39.     int vertices, wayValueCount, startFrom;
  40.     fin >> vertices >> wayValueCount >> startFrom;
  41.     startFrom--;
  42.     vector<vector<int>> w(vertices, vector<int>(vertices, intMax));
  43.     for (int i = 0; i < wayValueCount; i++) {
  44.         int from, to, value;
  45.         fin >> from >> to >> value;
  46.         from--, to--;
  47.         w[from][to] = value;
  48.     }
  49.     vector<int> dist;
  50.     dist = dijkstra(vertices, startFrom, w);
  51.     for (int i = 0; i < vertices; i++) {
  52.         if (dist[i] != intMax)
  53.             fout << dist[i] << ' ';
  54.         else
  55.             fout << "-1 ";
  56.     }
  57. }
Add Comment
Please, Sign In to add comment