#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;
class edge{
public:
int nb;
int wt;
edge(int nb,int wt)
{
this->nb = nb;
this->wt = wt;
}
};
vector<vector<edge>> graph;
void addedge(int v1,int v2,int w)
{
edge e(v2,w);
edge f(v1,w);
graph[v1].push_back(e);
graph[v2].push_back(f);
}
void addDedge(int v1,int v2,int w){
edge e(v2,w);
graph[v1].push_back(e);
}
void display()
{
for(int i=0;i<graph.size();i++)
{
cout<<i<<" -> ";
for(int j = 0;j<graph[i].size();j++)
{
cout<<" [" << graph[i][j].nb << "-" <<graph[i][j].wt <<"] ";
}
cout<<endl;
}
}
bool gcc(vector<bool>&visited,int s)
{
queue<int> q;
q.push(s);
while(q.size()>0)
{
int rem = q.front();
q.pop();
if(visited[rem]==true)
{
return true;
}
visited[rem] = true;
for(int i=0;i<graph[rem].size();i++)
{
if(visited[graph[rem][i].nb]==false)
{
q.push(graph[rem][i].nb);
}
}
}
return false;
}
bool gccc()
{
vector<bool>visited(graph.size(),false);
for(int i=0;i<graph.size();i++)
{
if(visited[i]==false)
{
bool ans = gcc(visited,i);
if(ans == true)
{
return true;
}
}
}
return false;
}
class edg{
public:
int x;
int lvl;
};
bool checkbip(vector<int>&visited,int s)
{
queue<edg> q;
edg start;
start.x = s;
start.lvl = 1;
int lvl = 1;
q.push(start);
while(q.size()>0)
{
edg rem = q.front();
q.pop();
if(visited[rem.x]!=0)
{
if(rem.lvl%2!=visited[rem.x]%2)
{
return false;
}
}
visited[rem.x] = rem.lvl;
for(int i=0;i<graph[rem.x].size();i++)
{
if(visited[graph[rem.x][i].nb]==0)
{
edg nbr;
nbr.x = graph[rem.x][i].nb;
nbr.lvl = rem.lvl + 1;
q.push(nbr);
}
}
}
return true;
}
bool isBipardite()
{
vector<int> visited(graph.size(),0);
for(int i=0;i<graph.size();i++)
{
if(visited[i]==0)
{
bool res = checkbip(visited,i);
if(res == false)
{
return false;
}
}
}
return true;
}
class element{
public:
int x;
int sum;
string ans;
element(int x,int sum,string ans)
{
this->x = x;
this->sum = sum;
this->ans = ans;
}
bool operator>(const element& e) const{
return this->sum > e.sum;
}
};
void dkt(int s)
{
priority_queue<element,vector<element>,greater<element>> q;
vector<bool> visited(graph.size(),false);
element start(s,0,to_string(s));
q.push(start);
while(q.size()>0)
{
element rem = q.top();
q.pop();
if(visited[rem.x]==true)
{
continue;
}
cout<<"Pos : "<< rem.x << " cost " << rem.sum << " Path :"<<rem.ans<<endl;
visited[rem.x] = true;
for(int i=0;i<graph[rem.x].size();i++)
{
if(visited[graph[rem.x][i].nb]==false)
{
element nn(graph[rem.x][i].nb ,
rem.sum + graph[rem.x][i].wt,
rem.ans + to_string(graph[rem.x][i].nb));
q.push(nn);
}
}
}
}
class pos{
public:
int x;
int step;
int total;
string asf;
pos(int x,int step,int total,string asf)
{
this->x = x;
this->step = step;
this->total = total;
this->asf = asf;
}
bool operator>(const pos& other) const{
return this->step > other.step;
}
};
void sl()
{
priority_queue<pos,vector<pos>,greater<pos>> q;
pos start(0,0,0,"0");
q.push(start);
vector<bool>visited(graph.size(),false);
while(q.size()>0)
{
pos rem = q.top();
q.pop();
if(rem.x == 29)
{
cout<< "pos : "<<rem.x<<" steps : "<<rem.step<<" total "<<rem.total<<" ansf : "<<rem.asf<<endl;
break;
}
if(visited[rem.x]==true)
{
continue;
}
visited[rem.x]=true;
for(int i=0;i<graph[rem.x].size();i++)
{
if(visited[graph[rem.x][i].nb]==false)
{
if(graph[rem.x][i].wt==0)
{
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));
q.push(newpos);
}
else
{
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));
q.push(newpos);
}
}
}
}
}
int main(int argc,char**argv)
{
// graph.push_back(vector<edge>());
// graph.push_back(vector<edge>());
// graph.push_back(vector<edge>());
// graph.push_back(vector<edge>());
// graph.push_back(vector<edge>());
// graph.push_back(vector<edge>());
// graph.push_back(vector<edge>());
// addedge(0,1,10);
// addedge(0,3,40);
// addedge(1,2,10);
// addedge(2,3,10);
// addedge(3,4,2);
// addedge(2,5,2);
// addedge(4,5,3);
// addedge(4,6,8);
// addedge(5,6,3);
for(int i=0;i<30;i++)
{
graph.push_back(vector<edge>());
}
for(int i=0;i<30;i++)
{
for(int j=1;j<=6;j++)
{
if(i+j<=29)
{
addDedge(i,i+j,j);
}
}
}
addDedge(2,21,0);
addDedge(4,7,0);
addDedge(10,25,0);
addDedge(19,28,0);
addDedge(26,0,0);
addDedge(20,8,0);
addDedge(16,3,0);
addDedge(18,6,0);
// display();
// cout<<isBipardite()<<endl;
// dkt(0);
sl();
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8cXVldWU+CiNpbmNsdWRlPHN0cmluZz4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyBlZGdlewoKICAgIHB1YmxpYzoKICAgICAgICBpbnQgbmI7CiAgICAgICAgaW50IHd0OwogICAgICAgIGVkZ2UoaW50IG5iLGludCB3dCkKICAgICAgICB7CiAgICAgICAgICAgIHRoaXMtPm5iID0gbmI7CiAgICAgICAgICAgIHRoaXMtPnd0ID0gd3Q7CiAgICAgICAgfQp9Owp2ZWN0b3I8dmVjdG9yPGVkZ2U+PiBncmFwaDsKdm9pZCBhZGRlZGdlKGludCB2MSxpbnQgdjIsaW50IHcpCnsKICAgIGVkZ2UgZSh2Mix3KTsKICAgIGVkZ2UgZih2MSx3KTsKICAgIGdyYXBoW3YxXS5wdXNoX2JhY2soZSk7CiAgICBncmFwaFt2Ml0ucHVzaF9iYWNrKGYpOwp9CnZvaWQgYWRkRGVkZ2UoaW50IHYxLGludCB2MixpbnQgdyl7CiAgICBlZGdlIGUodjIsdyk7CiAgICBncmFwaFt2MV0ucHVzaF9iYWNrKGUpOwp9Cgp2b2lkIGRpc3BsYXkoKQp7CiAgICBmb3IoaW50IGk9MDtpPGdyYXBoLnNpemUoKTtpKyspCiAgICB7CiAgICAgICAgY291dDw8aTw8IiAtPiAiOwogICAgICAgIGZvcihpbnQgaiA9IDA7ajxncmFwaFtpXS5zaXplKCk7aisrKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8IiBbIiA8PCBncmFwaFtpXVtqXS5uYiA8PCAiLSIgPDxncmFwaFtpXVtqXS53dCA8PCJdICI7CiAgICAgICAgfQogICAgICAgIGNvdXQ8PGVuZGw7CiAgICB9Cn0KCgpib29sIGdjYyh2ZWN0b3I8Ym9vbD4mdmlzaXRlZCxpbnQgcykKeyAgIAogICAgICAgIHF1ZXVlPGludD4gcTsKICAgICAgICBxLnB1c2gocyk7CiAgICAgICAgd2hpbGUocS5zaXplKCk+MCkKICAgICAgICB7CiAgICAgICAgCiAgICAgICAgaW50IHJlbSA9IHEuZnJvbnQoKTsKICAgICAgICBxLnBvcCgpOwogICAgICAgIGlmKHZpc2l0ZWRbcmVtXT09dHJ1ZSkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgIH0KICAgICAgICB2aXNpdGVkW3JlbV0gPSB0cnVlOwogICAgICAgIGZvcihpbnQgaT0wO2k8Z3JhcGhbcmVtXS5zaXplKCk7aSsrKQogICAgICAgIHsKICAgICAgICAgICBpZih2aXNpdGVkW2dyYXBoW3JlbV1baV0ubmJdPT1mYWxzZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgcS5wdXNoKGdyYXBoW3JlbV1baV0ubmIpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIGZhbHNlOyAgIAogICAgCn0KCgoKYm9vbCBnY2NjKCkKewogICAgdmVjdG9yPGJvb2w+dmlzaXRlZChncmFwaC5zaXplKCksZmFsc2UpOwogICAgZm9yKGludCBpPTA7aTxncmFwaC5zaXplKCk7aSsrKQogICAgewogICAgICAgIGlmKHZpc2l0ZWRbaV09PWZhbHNlKQogICAgICAgIHsKICAgICAgICAgICAgYm9vbCBhbnMgPSBnY2ModmlzaXRlZCxpKTsKICAgICAgICAgICAgaWYoYW5zID09IHRydWUpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgCiAgICAgICAgfQogICAgCiAgICB9CiAgICByZXR1cm4gZmFsc2U7Cn0KCmNsYXNzIGVkZ3sKICAgIHB1YmxpYzoKICAgIGludCB4OwogICAgaW50IGx2bDsKfTsKCmJvb2wgY2hlY2tiaXAodmVjdG9yPGludD4mdmlzaXRlZCxpbnQgcykKeyAgIAogICAgICAgIHF1ZXVlPGVkZz4gcTsKICAgICAgICBlZGcgc3RhcnQ7CiAgICAgICAgc3RhcnQueCA9IHM7CiAgICAgICAgc3RhcnQubHZsID0gMTsKICAgICAgICBpbnQgbHZsID0gMTsKICAgICAgICBxLnB1c2goc3RhcnQpOwogICAgICAgIHdoaWxlKHEuc2l6ZSgpPjApCiAgICAgICAgewogICAgICAgIAogICAgICAgIGVkZyByZW0gPSBxLmZyb250KCk7CiAgICAgICAgcS5wb3AoKTsKICAgICAgICBpZih2aXNpdGVkW3JlbS54XSE9MCkKICAgICAgICB7CiAgICAgICAgICAgaWYocmVtLmx2bCUyIT12aXNpdGVkW3JlbS54XSUyKQogICAgICAgICAgIHsKICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgdmlzaXRlZFtyZW0ueF0gPSByZW0ubHZsOwogICAgICAgIGZvcihpbnQgaT0wO2k8Z3JhcGhbcmVtLnhdLnNpemUoKTtpKyspCiAgICAgICAgewogICAgICAgICAgIGlmKHZpc2l0ZWRbZ3JhcGhbcmVtLnhdW2ldLm5iXT09MCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZWRnIG5icjsKICAgICAgICAgICAgICAgIG5ici54ID0gZ3JhcGhbcmVtLnhdW2ldLm5iOwogICAgICAgICAgICAgICAgbmJyLmx2bCA9IHJlbS5sdmwgKyAxOwoKICAgICAgICAgICAgIHEucHVzaChuYnIpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIH0gIAogICAgICAgIHJldHVybiB0cnVlOwp9CgoKYm9vbCBpc0JpcGFyZGl0ZSgpCnsKICAgIHZlY3RvcjxpbnQ+IHZpc2l0ZWQoZ3JhcGguc2l6ZSgpLDApOwogICAgZm9yKGludCBpPTA7aTxncmFwaC5zaXplKCk7aSsrKQogICAgewogICAgICAgIGlmKHZpc2l0ZWRbaV09PTApCiAgICAgICAgewogICAgICAgIGJvb2wgcmVzID0gY2hlY2tiaXAodmlzaXRlZCxpKTsKICAgICAgICBpZihyZXMgPT0gZmFsc2UpCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiB0cnVlOwogICAgCn0KCmNsYXNzIGVsZW1lbnR7CiAgICBwdWJsaWM6CiAgICBpbnQgeDsKICAgIGludCBzdW07CiAgICBzdHJpbmcgYW5zOwogICAgZWxlbWVudChpbnQgeCxpbnQgc3VtLHN0cmluZyBhbnMpCiAgICB7CiAgICAgICAgdGhpcy0+eCA9IHg7CiAgICAgICAgdGhpcy0+c3VtID0gc3VtOwogICAgICAgIHRoaXMtPmFucyA9IGFuczsKICAgIH0KCiAgICBib29sIG9wZXJhdG9yPihjb25zdCBlbGVtZW50JiBlKSBjb25zdHsKICAgICAgICByZXR1cm4gdGhpcy0+c3VtID4gZS5zdW07CiAgICB9CgoKfTsKCgp2b2lkIGRrdChpbnQgcykKewoKICAgIHByaW9yaXR5X3F1ZXVlPGVsZW1lbnQsdmVjdG9yPGVsZW1lbnQ+LGdyZWF0ZXI8ZWxlbWVudD4+IHE7CiAgICB2ZWN0b3I8Ym9vbD4gdmlzaXRlZChncmFwaC5zaXplKCksZmFsc2UpOwogICAgZWxlbWVudCBzdGFydChzLDAsdG9fc3RyaW5nKHMpKTsKICAgIHEucHVzaChzdGFydCk7CgogICAgd2hpbGUocS5zaXplKCk+MCkKICAgIHsKICAgICAgICBlbGVtZW50IHJlbSA9IHEudG9wKCk7CiAgICAgICAgcS5wb3AoKTsKICAgICAgICBpZih2aXNpdGVkW3JlbS54XT09dHJ1ZSkKICAgICAgICB7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICBjb3V0PDwiUG9zIDogIjw8IHJlbS54IDw8ICIgY29zdCAiIDw8IHJlbS5zdW0gPDwgIiBQYXRoIDoiPDxyZW0uYW5zPDxlbmRsOyAgCiAgICAgICAgdmlzaXRlZFtyZW0ueF0gPSB0cnVlOwoKICAgICAgICBmb3IoaW50IGk9MDtpPGdyYXBoW3JlbS54XS5zaXplKCk7aSsrKQogICAgICAgIHsKICAgICAgICAgICAgaWYodmlzaXRlZFtncmFwaFtyZW0ueF1baV0ubmJdPT1mYWxzZSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZWxlbWVudCBubihncmFwaFtyZW0ueF1baV0ubmIgLAogICAgICAgICAgICAgICAgIHJlbS5zdW0gKyBncmFwaFtyZW0ueF1baV0ud3QsIAogICAgICAgICAgICAgICAgIHJlbS5hbnMgKyB0b19zdHJpbmcoZ3JhcGhbcmVtLnhdW2ldLm5iKSk7CiAgICAgICAgICAgICAgICAgcS5wdXNoKG5uKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICAKfQoKY2xhc3MgcG9zewogICAgcHVibGljOgogICAgaW50IHg7CiAgICBpbnQgc3RlcDsKICAgIGludCB0b3RhbDsKICAgIHN0cmluZyBhc2Y7CgogICAgcG9zKGludCB4LGludCBzdGVwLGludCB0b3RhbCxzdHJpbmcgYXNmKQogICAgewogICAgICAgIHRoaXMtPnggPSB4OwogICAgICAgIHRoaXMtPnN0ZXAgPSBzdGVwOwogICAgICAgIHRoaXMtPnRvdGFsID0gdG90YWw7CiAgICAgICAgdGhpcy0+YXNmID0gYXNmOwogICAgfQogICAgYm9vbCBvcGVyYXRvcj4oY29uc3QgcG9zJiBvdGhlcikgY29uc3R7CgogICAgICAgIHJldHVybiB0aGlzLT5zdGVwID4gb3RoZXIuc3RlcDsKICAgIH0KCn07Cgp2b2lkIHNsKCkKewogICAgcHJpb3JpdHlfcXVldWU8cG9zLHZlY3Rvcjxwb3M+LGdyZWF0ZXI8cG9zPj4gcTsKICAgIHBvcyBzdGFydCgwLDAsMCwiMCIpOwogICAgcS5wdXNoKHN0YXJ0KTsKICAgIHZlY3Rvcjxib29sPnZpc2l0ZWQoZ3JhcGguc2l6ZSgpLGZhbHNlKTsKICAgIHdoaWxlKHEuc2l6ZSgpPjApCiAgICB7CiAgICAgICAgcG9zIHJlbSA9IHEudG9wKCk7CiAgICAgICAgcS5wb3AoKTsKICAgICAgICBpZihyZW0ueCA9PSAyOSkKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PCAicG9zIDogIjw8cmVtLng8PCIgc3RlcHMgOiAiPDxyZW0uc3RlcDw8IiB0b3RhbCAiPDxyZW0udG90YWw8PCIgYW5zZiA6ICI8PHJlbS5hc2Y8PGVuZGw7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICBpZih2aXNpdGVkW3JlbS54XT09dHJ1ZSkKICAgICAgICB7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICB2aXNpdGVkW3JlbS54XT10cnVlOwogICAgICAgIGZvcihpbnQgaT0wO2k8Z3JhcGhbcmVtLnhdLnNpemUoKTtpKyspCiAgICAgICAgewogICAgICAgICAgICBpZih2aXNpdGVkW2dyYXBoW3JlbS54XVtpXS5uYl09PWZhbHNlKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZihncmFwaFtyZW0ueF1baV0ud3Q9PTApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgIHBvcyBuZXdwb3MoZ3JhcGhbcmVtLnhdW2ldLm5iLHJlbS5zdGVwLHJlbS50b3RhbCtncmFwaFtyZW0ueF1baV0ud3QscmVtLmFzZisiICwgIit0b19zdHJpbmcoZ3JhcGhbcmVtLnhdW2ldLm5iKSk7CiAgICAgICAgICAgICAgICAgICAgIHEucHVzaChuZXdwb3MpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHBvcyBuZXdwb3MoZ3JhcGhbcmVtLnhdW2ldLm5iLHJlbS5zdGVwICsxICxyZW0udG90YWwrZ3JhcGhbcmVtLnhdW2ldLnd0LHJlbS5hc2YrIiAsICIrdG9fc3RyaW5nKGdyYXBoW3JlbS54XVtpXS5uYikpOwogICAgICAgICAgICAgICAgICAgIHEucHVzaChuZXdwb3MpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgCiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cgp9CgppbnQgbWFpbihpbnQgYXJnYyxjaGFyKiphcmd2KQp7CiAgICAvLyBncmFwaC5wdXNoX2JhY2sodmVjdG9yPGVkZ2U+KCkpOwogICAgLy8gZ3JhcGgucHVzaF9iYWNrKHZlY3RvcjxlZGdlPigpKTsKICAgIC8vIGdyYXBoLnB1c2hfYmFjayh2ZWN0b3I8ZWRnZT4oKSk7CiAgICAvLyBncmFwaC5wdXNoX2JhY2sodmVjdG9yPGVkZ2U+KCkpOwogICAgLy8gZ3JhcGgucHVzaF9iYWNrKHZlY3RvcjxlZGdlPigpKTsKICAgIC8vIGdyYXBoLnB1c2hfYmFjayh2ZWN0b3I8ZWRnZT4oKSk7CiAgICAvLyBncmFwaC5wdXNoX2JhY2sodmVjdG9yPGVkZ2U+KCkpOwogIAogICAgLy8gYWRkZWRnZSgwLDEsMTApOwogICAgLy8gYWRkZWRnZSgwLDMsNDApOwogICAgLy8gYWRkZWRnZSgxLDIsMTApOwogICAgLy8gYWRkZWRnZSgyLDMsMTApOwogICAgLy8gYWRkZWRnZSgzLDQsMik7CiAgICAvLyBhZGRlZGdlKDIsNSwyKTsKICAgIC8vIGFkZGVkZ2UoNCw1LDMpOwogICAgLy8gYWRkZWRnZSg0LDYsOCk7CiAgICAvLyBhZGRlZGdlKDUsNiwzKTsKCiAgICBmb3IoaW50IGk9MDtpPDMwO2krKykKICAgIHsKICAgICAgICBncmFwaC5wdXNoX2JhY2sodmVjdG9yPGVkZ2U+KCkpOwogICAgfQogICAgZm9yKGludCBpPTA7aTwzMDtpKyspCiAgICB7CiAgICAgICAgZm9yKGludCBqPTE7ajw9NjtqKyspCiAgICAgICAgewogICAgICAgICAgIGlmKGkrajw9MjkpCiAgICAgICAgICAgewogICAgICAgICAgIGFkZERlZGdlKGksaStqLGopOwogICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgYWRkRGVkZ2UoMiwyMSwwKTsKICAgIGFkZERlZGdlKDQsNywwKTsKICAgIGFkZERlZGdlKDEwLDI1LDApOwogICAgYWRkRGVkZ2UoMTksMjgsMCk7CgogICAgYWRkRGVkZ2UoMjYsMCwwKTsKICAgIGFkZERlZGdlKDIwLDgsMCk7CiAgICBhZGREZWRnZSgxNiwzLDApOwogICAgYWRkRGVkZ2UoMTgsNiwwKTsKCiAgICAvLyBkaXNwbGF5KCk7IAogICAgLy8gY291dDw8aXNCaXBhcmRpdGUoKTw8ZW5kbDsKICAgIC8vIGRrdCgwKTsKCiAgICBzbCgpOwoKfQ==