SHARE
TWEET

Dijkstra2D

a guest Jun 25th, 2019 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define PI 3.14159265358979323846
  3. #define mod 998244353
  4. #define INF 999999999
  5. #define MAX 110
  6. #define f first
  7. #define s second
  8. #define ll long long
  9. #define pb push_back
  10. #define mp make_pair
  11. #define pii pair<int, int>
  12. #define vi vector<int>
  13. #define vii vector< pair<int,int> >
  14. #define sws ios_base::sync_with_stdio(false)
  15. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  16. #define endl '\n'
  17.  
  18. using namespace std;
  19.  
  20. // https://neps.academy/lesson/215
  21.  
  22. typedef struct
  23. {
  24.     int dist;
  25.     int x, y;
  26. } vertice;
  27.  
  28. struct Comp // Peguei na internet lol
  29. {
  30.     bool operator()(vertice& a, vertice& b)
  31.     {
  32.         return a.dist > b.dist;
  33.     }
  34. };
  35.  
  36. int N;
  37. bool mat[MAX][MAX], visitado[MAX][MAX];
  38. int distancia[MAX][MAX];
  39.  
  40. int coordx[4]={0,1,0,-1};
  41. int coordy[4]={1,0,-1,0};
  42.  
  43. void dijkstra(int i, int j)
  44. {
  45.     int a, b;
  46.     vertice aux, aux2;
  47.  
  48.     aux.dist=0;
  49.     aux.x=i;
  50.     aux.y=j;
  51.  
  52.     priority_queue< vertice, vector<vertice>, Comp >fila;
  53.     fila.push(aux);
  54.  
  55.     while(!fila.empty())
  56.     {
  57.         aux=fila.top();
  58.         fila.pop();
  59.         if(!visitado[aux.x][aux.y])
  60.         {
  61.             visitado[aux.x][aux.y]=true;
  62.             distancia[aux.x][aux.y]=aux.dist;
  63.  
  64.             for(int i=0;i<4;i++)
  65.             {
  66.                 a=aux.x+coordx[i];
  67.                 b=aux.y+coordy[i];
  68.                
  69.                 if(a>=0 and b>=0 and a<N and b<N and !visitado[a][b])
  70.                 {
  71.                     aux2.x=a;aux2.y=b;
  72.                     aux2.dist=aux.dist+mat[a][b];
  73.                     fila.push(aux2);
  74.                 }
  75.             }
  76.         }
  77.     }
  78. }
  79.  
  80. int main()
  81. {  
  82.     sws;
  83.     cin >> N;
  84.  
  85.     forn(i,N)
  86.         forn(j,N)
  87.         {
  88.             cin >> mat[i][j];
  89.             visitado[MAX][MAX]=false;
  90.             distancia[i][j]=INF;
  91.         }
  92.  
  93.     distancia[0][0]=0;
  94.     dijkstra(0,0);
  95.  
  96.     cout << distancia[N-1][N-1] << endl;
  97.  
  98.     return 0;
  99. }
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