fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include <cstring>
  5. #include<climits>
  6.  
  7. using namespace std;
  8. int a[100][100], vs[100], n, d[100], truoc[100];
  9. int MAX = 999999;
  10.  
  11. void dijkstra(int start) {
  12.   d[start] = 0;
  13.   vs[start] = 1;
  14.   for (int i = 1; i <= n; i++) {
  15.     d[i] = a[start][i];
  16.     truoc[i] = start;
  17.   }
  18.   while (true) {
  19.     for (int i = 1; i <= n; i++) cout << d[i] << "|" << truoc[i] << " ";
  20.     cout << endl;
  21.     int u = 0, min = MAX;
  22.     for (int i = 1; i <= n; i++) {
  23.         if (!vs[i] && d[i] < min) {
  24.             u = i;
  25.             min = d[i];
  26.         }
  27.     }
  28.     if (u == 0) break;
  29.     cout << "Tham dinh: " << u << endl;
  30.     vs[u] = 1;
  31.     for (int i = 1; i <= n; i++) {
  32.         if (!vs[i] && d[i] > d[u] + a[u][i]) {
  33.             d[i] = d[u] + a[u][i];
  34.             truoc[i] = u;
  35.         }
  36.     }
  37.   }
  38. }
  39.  
  40. int main() {
  41.     cout << "So dinh: ";
  42.     cin >> n;
  43.     // Khoi tao ma tran ke
  44.     cout << "Nhap ma tran:\n";
  45.     memset(vs, 0, sizeof(vs));
  46.  
  47.     for (int i = 1; i <= n; i++) {
  48.         for (int j = 1; j <= n; j++) {
  49.             cin >> a[i][j];
  50.             if (a[i][j] == 0 && i != j) a[i][j] = MAX;
  51.  
  52.         }
  53.     }
  54.     int start, goal;
  55.     cout << "Bat dau: ";
  56.     cin >> start;
  57.     dijkstra(start);
  58.  
  59. }
  60.  
  61. /**
  62. Test:
  63.  
  64. 5
  65. 0 7 5 8 2
  66. 0 0 0 0 0
  67. 0 1 0 1 0
  68. 0 1 0 0 0
  69. 0 0 0 1 0
  70.  
  71.  
  72.  
  73. 5
  74. 0 2 0 8 5
  75. 2 0 1 3 0
  76. 0 1 3 1 0
  77. 8 3 1 0 1
  78. 5 0 0 1 0
  79.  
  80.  
  81. **/
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
So dinh: Nhap ma tran:
Bat dau:
https://ideone.com/hu3Lgu
language:
C++ (gcc 8.3)
created:
7 days 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!