fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #include<string>
  5.  
  6. using namespace std;
  7.  
  8. class edge{
  9.  
  10.     public:
  11.         int nb;
  12.         int wt;
  13.         edge(int nb,int wt)
  14.         {
  15.             this->nb = nb;
  16.             this->wt = wt;
  17.         }
  18. };
  19. vector<vector<edge>> graph;
  20. void addedge(int v1,int v2,int w)
  21. {
  22.     edge e(v2,w);
  23.     edge f(v1,w);
  24.     graph[v1].push_back(e);
  25.     graph[v2].push_back(f);
  26. }
  27. void addDedge(int v1,int v2,int w){
  28.     edge e(v2,w);
  29.     graph[v1].push_back(e);
  30. }
  31.  
  32. void display()
  33. {
  34.     for(int i=0;i<graph.size();i++)
  35.     {
  36.         cout<<i<<" -> ";
  37.         for(int j = 0;j<graph[i].size();j++)
  38.         {
  39.             cout<<" [" << graph[i][j].nb << "-" <<graph[i][j].wt <<"] ";
  40.         }
  41.         cout<<endl;
  42.     }
  43. }
  44.  
  45.  
  46. bool gcc(vector<bool>&visited,int s)
  47. {   
  48.         queue<int> q;
  49.         q.push(s);
  50.         while(q.size()>0)
  51.         {
  52.  
  53.         int rem = q.front();
  54.         q.pop();
  55.         if(visited[rem]==true)
  56.         {
  57.             return true;
  58.         }
  59.         visited[rem] = true;
  60.         for(int i=0;i<graph[rem].size();i++)
  61.         {
  62.            if(visited[graph[rem][i].nb]==false)
  63.             {
  64.              q.push(graph[rem][i].nb);
  65.             }
  66.         }
  67.         }
  68.  
  69.         return false;   
  70.  
  71. }
  72.  
  73.  
  74.  
  75. bool gccc()
  76. {
  77.     vector<bool>visited(graph.size(),false);
  78.     for(int i=0;i<graph.size();i++)
  79.     {
  80.         if(visited[i]==false)
  81.         {
  82.             bool ans = gcc(visited,i);
  83.             if(ans == true)
  84.             {
  85.                 return true;
  86.             }
  87.  
  88.         }
  89.  
  90.     }
  91.     return false;
  92. }
  93.  
  94. class edg{
  95.     public:
  96.     int x;
  97.     int lvl;
  98. };
  99.  
  100. bool checkbip(vector<int>&visited,int s)
  101. {   
  102.         queue<edg> q;
  103.         edg start;
  104.         start.x = s;
  105.         start.lvl = 1;
  106.         int lvl = 1;
  107.         q.push(start);
  108.         while(q.size()>0)
  109.         {
  110.  
  111.         edg rem = q.front();
  112.         q.pop();
  113.         if(visited[rem.x]!=0)
  114.         {
  115.            if(rem.lvl%2!=visited[rem.x]%2)
  116.            {
  117.                return false;
  118.            }
  119.         }
  120.         visited[rem.x] = rem.lvl;
  121.         for(int i=0;i<graph[rem.x].size();i++)
  122.         {
  123.            if(visited[graph[rem.x][i].nb]==0)
  124.             {
  125.                 edg nbr;
  126.                 nbr.x = graph[rem.x][i].nb;
  127.                 nbr.lvl = rem.lvl + 1;
  128.  
  129.              q.push(nbr);
  130.             }
  131.         }
  132.         }  
  133.         return true;
  134. }
  135.  
  136.  
  137. bool isBipardite()
  138. {
  139.     vector<int> visited(graph.size(),0);
  140.     for(int i=0;i<graph.size();i++)
  141.     {
  142.         if(visited[i]==0)
  143.         {
  144.         bool res = checkbip(visited,i);
  145.         if(res == false)
  146.         {
  147.             return false;
  148.         }
  149.         }
  150.     }
  151.     return true;
  152.  
  153. }
  154.  
  155. class element{
  156.     public:
  157.     int x;
  158.     int sum;
  159.     string ans;
  160.     element(int x,int sum,string ans)
  161.     {
  162.         this->x = x;
  163.         this->sum = sum;
  164.         this->ans = ans;
  165.     }
  166.  
  167.     bool operator>(const element& e) const{
  168.         return this->sum > e.sum;
  169.     }
  170.  
  171.  
  172. };
  173.  
  174.  
  175. void dkt(int s)
  176. {
  177.  
  178.     priority_queue<element,vector<element>,greater<element>> q;
  179.     vector<bool> visited(graph.size(),false);
  180.     element start(s,0,to_string(s));
  181.     q.push(start);
  182.  
  183.     while(q.size()>0)
  184.     {
  185.         element rem = q.top();
  186.         q.pop();
  187.         if(visited[rem.x]==true)
  188.         {
  189.             continue;
  190.         }
  191.         cout<<"Pos : "<< rem.x << " cost " << rem.sum << " Path :"<<rem.ans<<endl;  
  192.         visited[rem.x] = true;
  193.  
  194.         for(int i=0;i<graph[rem.x].size();i++)
  195.         {
  196.             if(visited[graph[rem.x][i].nb]==false)
  197.             {
  198.                 element nn(graph[rem.x][i].nb ,
  199.                  rem.sum + graph[rem.x][i].wt, 
  200.                  rem.ans + to_string(graph[rem.x][i].nb));
  201.                  q.push(nn);
  202.             }
  203.         }
  204.     }
  205.  
  206.  
  207. }
  208.  
  209. class pos{
  210.     public:
  211.     int x;
  212.     int step;
  213.     int total;
  214.     string asf;
  215.  
  216.     pos(int x,int step,int total,string asf)
  217.     {
  218.         this->x = x;
  219.         this->step = step;
  220.         this->total = total;
  221.         this->asf = asf;
  222.     }
  223.     bool operator>(const pos& other) const{
  224.  
  225.         return this->step > other.step;
  226.     }
  227.  
  228. };
  229.  
  230. void sl()
  231. {
  232.     priority_queue<pos,vector<pos>,greater<pos>> q;
  233.     pos start(0,0,0,"0");
  234.     q.push(start);
  235.     vector<bool>visited(graph.size(),false);
  236.     while(q.size()>0)
  237.     {
  238.         pos rem = q.top();
  239.         q.pop();
  240.         if(rem.x == 29)
  241.         {
  242.             cout<< "pos : "<<rem.x<<" steps : "<<rem.step<<" total "<<rem.total<<" ansf : "<<rem.asf<<endl;
  243.             break;
  244.         }
  245.         if(visited[rem.x]==true)
  246.         {
  247.             continue;
  248.         }
  249.         visited[rem.x]=true;
  250.         for(int i=0;i<graph[rem.x].size();i++)
  251.         {
  252.             if(visited[graph[rem.x][i].nb]==false)
  253.             {
  254.                 if(graph[rem.x][i].wt==0)
  255.                 {
  256.                      pos newpos(graph[rem.x][i].nb,rem.step,rem.total+graph[rem.x][i].wt,rem.asf+" , "+to_string(graph[rem.x][i].nb));
  257.                      q.push(newpos);
  258.                 }
  259.                 else
  260.                 {
  261.                     pos newpos(graph[rem.x][i].nb,rem.step +1 ,rem.total+graph[rem.x][i].wt,rem.asf+" , "+to_string(graph[rem.x][i].nb));
  262.                     q.push(newpos);
  263.                 }
  264.  
  265.  
  266.  
  267.             }
  268.         }
  269.     }
  270.  
  271. }
  272.  
  273. int main(int argc,char**argv)
  274. {
  275.     // graph.push_back(vector<edge>());
  276.     // graph.push_back(vector<edge>());
  277.     // graph.push_back(vector<edge>());
  278.     // graph.push_back(vector<edge>());
  279.     // graph.push_back(vector<edge>());
  280.     // graph.push_back(vector<edge>());
  281.     // graph.push_back(vector<edge>());
  282.  
  283.     // addedge(0,1,10);
  284.     // addedge(0,3,40);
  285.     // addedge(1,2,10);
  286.     // addedge(2,3,10);
  287.     // addedge(3,4,2);
  288.     // addedge(2,5,2);
  289.     // addedge(4,5,3);
  290.     // addedge(4,6,8);
  291.     // addedge(5,6,3);
  292.  
  293.     for(int i=0;i<30;i++)
  294.     {
  295.         graph.push_back(vector<edge>());
  296.     }
  297.     for(int i=0;i<30;i++)
  298.     {
  299.         for(int j=1;j<=6;j++)
  300.         {
  301.            if(i+j<=29)
  302.            {
  303.            addDedge(i,i+j,j);
  304.            }
  305.         }
  306.     }
  307.  
  308.     addDedge(2,21,0);
  309.     addDedge(4,7,0);
  310.     addDedge(10,25,0);
  311.     addDedge(19,28,0);
  312.  
  313.     addDedge(26,0,0);
  314.     addDedge(20,8,0);
  315.     addDedge(16,3,0);
  316.     addDedge(18,6,0);
  317.  
  318.     // display(); 
  319.     // cout<<isBipardite()<<endl;
  320.     // dkt(0);
  321.  
  322.     sl();
  323.  
  324. }
Success #stdin #stdout 0s 15256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
pos : 29 steps : 3 total 10 ansf : 0 , 2 , 21 , 24 , 29
https://ideone.com/rIxTa0
language:
C++ (gcc 8.3)
created:
4 years 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!