ulvis.paste.net

Paste Search Dynamic
Recent pastes
solve
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define for1(i,a,b) for(int i=a;i<=b;i++)
  4.  
  5. int T;
  6.  
  7. void enter()
  8. {
  9.     cin>>T;
  10. }
  11.  
  12. void init(int **&graph,int n)
  13. {
  14.     graph=new int*[n+1];
  15.     for1(i,0,n) graph[i]=new int[n+1];
  16.     for1(i,1,n)
  17.         for1(j,1,n)
  18.             if (j==i+1||j==3*i) graph[i][j]=1;
  19.             else graph[i][j]=0;
  20. }
  21.  
  22. int minDistance(int *dist,bool *sptSet,int n)
  23. {
  24.     int min,minIndex;
  25.     min=int_max;
  26.     for1(v,0,n-1)
  27.         if (!sptSet[v]&&dist[v]<min)
  28.         {
  29.             min=dist[v];
  30.             minIndex=v;
  31.         }
  32.     return minIndex;
  33. }
  34.  
  35. void dijkstra(int **graph,int s,int n)
  36. {
  37.     int u;
  38.     int *dist;
  39.     bool *sptSet;
  40.     dist=new int[n+1];
  41.     sptSet=new bool[n+1];
  42.     for1(i,1,n)
  43.     {
  44.         sptSet[i]=0;
  45.         dist[i]=int_max;
  46.     }
  47.     dist[s]=0;
  48.     for1(count,1,n-1)
  49.     {
  50.         u=minDistance(dist,sptSet,n);
  51.         sptSet[u]=1;
  52.         for1(v,1,n)
  53.             if (!sptSet[v]&&graph[u][v]&&dist[u]+graph[u][v]<dist[v]) dist[v]=dist[u]+graph[u][v];
  54.     }
  55.     cout<<dist[n]<<'\n';
  56. }
  57.  
  58. void clean(int **&graph,int n)
  59. {
  60.     for1(i,0,n) delete[] graph[i];
  61.     delete[] graph;
  62. }
  63.  
  64. void solve()
  65. {
  66.     int n;
  67.     int **graph;
  68.     while (T--)
  69.     {
  70.         cin>>n;
  71.         init(graph,n);
  72.         dijkstra(graph,1,n);
  73.         clean(graph,n);
  74.     }
  75. }
  76.  
  77. int main()
  78. {
  79.     enter();
  80.     solve();
  81. }
  82.  
  83.  
Parsed in 0.010 seconds