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 #stderr 0s 80768KB
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 -213934816
1 -213934812
2 -213934808
3 2147483647
4 2147483647
0 -427869632
1 -427869628
2 -427869624
3 2147483647
4 2147483647
0 -641804448
1 -641804444
2 -641804440
3 2147483647
4 2147483647
0 -855739264
1 -855739260
2 -855739256
3 2147483647
4 2147483647
stderr
copy 
*** Error in `./prog': double free or corruption (out): 0x000055e3f33f9c60 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x70bcb)[0x2b11fb89fbcb]
/lib/x86_64-linux-gnu/libc.so.6(+0x76f96)[0x2b11fb8a5f96]
/lib/x86_64-linux-gnu/libc.so.6(+0x7778e)[0x2b11fb8a678e]
./prog(+0xd2f)[0x55e3f2833d2f]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf1)[0x2b11fb84f2b1]
./prog(+0xdba)[0x55e3f2833dba]
======= Memory map: ========
2b11fab4f000-2b11fab72000 r-xp 00000000 fd:00 2710543                    /lib/x86_64-linux-gnu/ld-2.24.so
2b11fab72000-2b11fab76000 rw-p 00000000 00:00 0 
2b11fab7f000-2b11fab84000 rw-p 00000000 00:00 0 
2b11fad72000-2b11fad73000 r--p 00023000 fd:00 2710543                    /lib/x86_64-linux-gnu/ld-2.24.so
2b11fad73000-2b11fad74000 rw-p 00024000 fd:00 2710543                    /lib/x86_64-linux-gnu/ld-2.24.so
2b11fad74000-2b11fad75000 rw-p 00000000 00:00 0 
2b11fad75000-2b11faee7000 r-xp 00000000 fd:00 2712611                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2b11faee7000-2b11fb0e7000 ---p 00172000 fd:00 2712611                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2b11fb0e7000-2b11fb0f1000 r--p 00172000 fd:00 2712611                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2b11fb0f1000-2b11fb0f3000 rw-p 0017c000 fd:00 2712611                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2b11fb0f3000-2b11fb0f7000 rw-p 00000000 00:00 0 
2b11fb0f7000-2b11fb1fa000 r-xp 00000000 fd:00 2710572                    /lib/x86_64-linux-gnu/libm-2.24.so
2b11fb1fa000-2b11fb3f9000 ---p 00103000 fd:00 2710572                    /lib/x86_64-linux-gnu/libm-2.24.so
2b11fb3f9000-2b11fb3fa000 r--p 00102000 fd:00 2710572                    /lib/x86_64-linux-gnu/libm-2.24.so
2b11fb3fa000-2b11fb3fb000 rw-p 00103000 fd:00 2710572                    /lib/x86_64-linux-gnu/libm-2.24.so
2b11fb3fb000-2b11fb411000 r-xp 00000000 fd:00 2710510                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2b11fb411000-2b11fb610000 ---p 00016000 fd:00 2710510                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2b11fb610000-2b11fb611000 r--p 00015000 fd:00 2710510                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2b11fb611000-2b11fb612000 rw-p 00016000 fd:00 2710510                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2b11fb612000-2b11fb62a000 r-xp 00000000 fd:00 2710529                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2b11fb62a000-2b11fb829000 ---p 00018000 fd:00 2710529                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2b11fb829000-2b11fb82a000 r--p 00017000 fd:00 2710529                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2b11fb82a000-2b11fb82b000 rw-p 00018000 fd:00 2710529                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2b11fb82b000-2b11fb82f000 rw-p 00000000 00:00 0 
2b11fb82f000-2b11fb9c4000 r-xp 00000000 fd:00 2710666                    /lib/x86_64-linux-gnu/libc-2.24.so
2b11fb9c4000-2b11fbbc3000 ---p 00195000 fd:00 2710666                    /lib/x86_64-linux-gnu/libc-2.24.so
2b11fbbc3000-2b11fbbc7000 r--p 00194000 fd:00 2710666                    /lib/x86_64-linux-gnu/libc-2.24.so
2b11fbbc7000-2b11fbbc9000 rw-p 00198000 fd:00 2710666                    /lib/x86_64-linux-gnu/libc-2.24.so
2b11fbbc9000-2b11fbbcd000 rw-p 00000000 00:00 0 
2b11fc000000-2b11fc021000 rw-p 00000000 00:00 0 
2b11fc021000-2b1200000000 ---p 00000000 00:00 0 
55e3f2833000-55e3f2835000 r-xp 00000000 fd:00 25030660                   /home/kYdBlF/prog
55e3f2a34000-55e3f2a35000 r--p 00001000 fd:00 25030660                   /home/kYdBlF/prog
55e3f2a35000-55e3f2a36000 rw-p 00002000 fd:00 25030660                   /home/kYdBlF/prog
55e3f33e7000-55e3f3419000 rw-p 00000000 00:00 0                          [heap]
7ffd05785000-7ffd057a6000 rw-p 00000000 00:00 0                          [stack]
7ffd057cc000-7ffd057ce000 r-xp 00000000 00:00 0                          [vdso]
7ffd057ce000-7ffd057d0000 r--p 00000000 00:00 0                          [vvar]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
https://ideone.com/9rAyhB
language:
C++ (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!