fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <climits>
  4.  
  5. using namespace std;
  6.  
  7. int findminvertex(int *distance, bool *visited, int n)
  8. {
  9.       int minvertex = -1;
  10.       for (int i = 0; i < n; i++)
  11.       {
  12.             if (!visited[i] && (minvertex == -1 || distance[i] < distance[minvertex]))
  13.             {
  14.                   minvertex = i;
  15.             }
  16.       }
  17.       return minvertex;
  18. }
  19.  
  20. void dijistra(int **edges, int n)
  21. {
  22.       int *distance = new int[n];
  23.       bool *visited = new bool[n];
  24.       for (int i = 0; i < n; i++){
  25.             distance[i] = INT_MAX;
  26.             visited[i] = false;
  27.       }
  28.  
  29.       distance[0] = 0;
  30.       for (int i = 0; i < n - 1; i++){
  31.             int minvertex = findminvertex(distance, visited, n);
  32.             for (int j = 0; j < n; j++){
  33.                   if (edges[minvertex][j] != 0 && !visited[j])
  34.                   {
  35.                         int dist = distance[minvertex] + edges[minvertex][j];
  36.                         if (dist < distance[j])
  37.                         {
  38.                               distance[j] = dist;
  39.                         }
  40.                   }
  41.             }
  42.             for (int i = 0; i < n; i++)
  43.             {
  44.                   cout << i << " " << distance[i] << endl;
  45.             }
  46.             delete[] visited;
  47.             delete[] distance;
  48.       }
  49. }
  50.  
  51. int main(){
  52.       int n;
  53.       int e;
  54.       cin >> n >> e;
  55.       int **edges = new int *[n];
  56.       for (int i = 0; i < e; i++)
  57.       {
  58.             edges[i] = new int[n];
  59.             for (int j = 0; j < n; j++)
  60.             {
  61.                   edges[i][j] = 0;
  62.             }
  63.       }
  64.  
  65.       for (int i = 0; i < e; i++)
  66.       {
  67.             int f, s, weight;
  68.             cin >> f >> s >> weight;
  69.             edges[f][s] = weight;
  70.             edges[s][f] = weight;
  71.       }
  72.       cout << endl;
  73.       dijistra(edges, n);
  74.       for (int i = 0; i < e; i++)
  75.       {
  76.             delete[] edges[i];
  77.       }
  78.       delete[] edges;
  79. }
  80.  
Runtime error #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5 7
0 1 4
0 2 8
1 3 5
1 2 2
2 3 5
2 4 9
3 4 4
stdout
copy 
0 0
1 4
2 8
3 2147483647
4 2147483647
0 16
1 10
2 8
3 13
4 17
https://ideone.com/j1ApE5
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!