SHARE
TWEET

Untitled

a guest Jan 14th, 2020 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. static void Dijkstry(int s, int n, int** A, int* dist, int* pred)
  7. {
  8.     int* fin = new int[n];
  9.     int inf=1000000;
  10.     for(int v=0; v<n; v++)
  11.     {
  12.         dist[v]=inf;
  13.         fin[v]=0;
  14.         pred[v]=-1;
  15.     }
  16.     dist[s]=0;
  17.     fin[s]=1;
  18.     int last=s;
  19.     for(int i=1; i<n; i++)
  20.     {
  21.         for(int v=0; v<n; v++)
  22.             if(A[last][v]<inf && fin[v]==0)
  23.             {
  24.                 if(dist[last]+A[last][v]<dist[v])
  25.                 {
  26.                     dist[v]=dist[last]+A[last][v];
  27.                     pred[v]=last+1;
  28.                 }
  29.             }
  30.         int y=0, temp=inf;
  31.         for(int u=0; u<n; u++)
  32.         {
  33.             if((fin[u]==0)&&(dist[u]<temp))
  34.             {
  35.                 y=u;
  36.                 temp=dist[u];
  37.             }
  38.         }
  39.         if(temp<inf)
  40.         {
  41.             fin[y]=1;
  42.             last=y;
  43.         }
  44.     }
  45. }
  46.  
  47. int main()
  48. {
  49.     int n, m;
  50.     ifstream wejscie("In0304.txt");
  51.     wejscie >> n >> m;
  52.  
  53.     int s=m-1;
  54.     cout << n << ' ' << s << endl;
  55.  
  56.     int** A = new int*[n];
  57.     for(int i=0; i<n; i++)
  58.         A[i] = new int[n];
  59.  
  60.     for (int i=0; i<n; i++)
  61.         for (int j=0; j<n; j++)
  62.             wejscie >> A[i][j];
  63.     wejscie.close();
  64.  
  65.     for (int i=0; i<n; i++)
  66.     {
  67.         for (int j=0; j<n; j++)
  68.             cout << A[i][j] << ' ';
  69.         cout << endl;
  70.     }
  71.  
  72.     int dist[n];
  73.     int pred[n];
  74.  
  75.     Dijkstry(s, n, A, dist, pred);
  76.  
  77.     ofstream wyjscie("Out0304.txt");
  78.     wyjscie << "dist[";
  79.     for (int i=0; i<n; i++)
  80.     {
  81.         wyjscie << dist[i];
  82.         if(i<n-1)
  83.             wyjscie << " ";
  84.     }
  85.     wyjscie << ']' << endl << "pred[";
  86.     for (int i=0; i<n; i++)
  87.     {
  88.         wyjscie << pred[i];
  89.         if(i<n-1)
  90.             wyjscie << " ";
  91.     }
  92.     wyjscie << ']';
  93.  
  94.     wyjscie.close();
  95.  
  96.     return 0;
  97. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top