SHARE
TWEET

Dijkstra old

nguyenvanquan7826 May 25th, 2014 855 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define INP "input.inp"
  4. #define OUT "output.out"
  5. int main()
  6. {
  7.         FILE *f = fopen(INP, "r");
  8.         int n, a, b, i, sum = 0;
  9.         fscanf(f,"%d%d%d", &n, &a, &b);
  10.         int G[n][n];
  11.         int s[n], Len[n], P[n];
  12.        
  13.         for (i = 0; i<n; i++)           // nhap ma tran
  14.                 for (int j=0; j<n; j++)
  15.                 {
  16.                         fscanf(f, "%d", &G[i][j]);
  17.                         sum += G[i][j];
  18.                 }
  19.         for (int i=0; i<n; i++)         // dat vo cung bang tong gia tri ma tran
  20.         {
  21.                 for (int j=0; j<n; j++)
  22.                 {
  23.                         printf("%3d", G[i][j]);
  24.                         if (G[i][j] == 0) G[i][j] = sum;
  25.                 }
  26.                 printf("\n");
  27.         }
  28.        
  29.         for (int i=0; i<n; i++)
  30.         {
  31.                 Len[i] = sum;           // do dai den diem i
  32.                 s[i] = 0;                       // danh sach cac diem da xet
  33.                 P[i] = a;                       // dat diem bat dau cua moi diem la a
  34.         }
  35.        
  36.         Len[a] = 0;                             // dat do dai tu a -> a la 0
  37.        
  38.         while (s[b] == 0)               // trong khi diem cuoi chua duoc xet
  39.         {
  40.                 for (i=0; i<n; i++)     // tim 1 vi tri ma khong phai la vo cung
  41.                         if (!s[i] && Len[i] < sum)
  42.                                 break;
  43.                 if (i >= n) break;
  44.                 for (int j=0; j<n; j++) // tim diem co vi tri ma do dai la min
  45.                         if (!s[j] && Len[i] > Len[j])
  46.                                 i = j;
  47.                
  48.                 s[i] = 1;       // cho i vao danh sach xet roi
  49.                 for (int j=0; j<n; j++) // dubet tinh lai do dai cua cac diem chua xet
  50.                         if (!s[j] && Len[i] + G[i][j] < Len[j])
  51.                         {
  52.                                 Len[j] = Len[i] + G[i][j];      // thay doi len
  53.                                 P[j] = i;       // danh dau diem truoc no
  54.                         }
  55.         }
  56.        
  57.         printf("\nLength of %d to %d is %d\n",a, b, Len[b]);
  58.        
  59.         // truy vet
  60.         i = b;
  61.         while (i != a)
  62.         {
  63.                 printf("%d <-- ", i);
  64.                 i = P[i];
  65.         }
  66.         printf("%d", a);
  67.        
  68.         return 0;
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top