fork download
copy 
  1.  
  2.  
  3.  
  4. #include<iostream>
  5. #include<queue>
  6. #include<cstdlib>
  7. #include<cstring>
  8.  
  9. using namespace std;
  10.  
  11. #define p1 pair<int,p2>
  12. #define p2 pair<int,int>
  13. #define x  second.first
  14. #define y  second.second
  15. #define    cost first
  16.  
  17. int main()
  18. {
  19.    //priority_queue<p1>q;
  20.    priority_queue<p1,vector<p1>,greater<p1> >q;
  21.  
  22.     int n,i,j,k=1;
  23.     int dx[]={1,1,0,1};
  24.     int dy[]={0,1,1,-1};
  25.     while(1)
  26.     {
  27.     cin>>n;
  28.     if(n==0)
  29.         break;
  30.     int c[n+10][n+10];
  31.     int vis[n+10][n+10];
  32.     for(i=0;i<n;i++)
  33.     {
  34.         for(j=0;j<3;j++)
  35.         {
  36.  
  37.         cin>>c[i][j];
  38.  
  39.         }
  40.  
  41.     }
  42.     q.push(p1(c[0][1],p2(0,1)));
  43.     memset(vis,0,sizeof(vis));
  44.        while(!q.empty())
  45.  
  46. {
  47.     p1 temp=q.top();
  48.     q.pop();
  49.    // cout<<" x "<<temp.x<<" y "<<temp.y<<" "<<temp.cost<<endl;
  50.     vis[temp.x][temp.y]=1;
  51.  
  52.     if(temp.x==n-1 && temp.y==1)
  53.     {
  54.         cout<<k<<". "<<temp.cost<<endl;
  55.         break;
  56.     }
  57.     for(i=0;i<4;i++)
  58.     {
  59.         int nx= temp.x+dx[i];
  60.         int ny=temp.y+dy[i];
  61.  
  62.         if(nx<=n-1&&nx>=0&&ny<=2&&ny>=0&&!vis[nx][ny])
  63.         {
  64.             //cout<<" cost "<<temp.cost<< " "<<c[nx][ny]<<endl;
  65.             q.push(p1((temp.cost+c[nx][ny]),p2(nx,ny)));
  66.         }
  67.  
  68.     }
  69.  
  70.  
  71. }
  72. k++;
  73.  
  74.     }
  75.  
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
4
13 7 5
7 13 6
14 3 12
15 6 16
2 
4 5 6 
4 4 4 
2 
-1 -1 -1 
-1 -1 -1 
0
stdout
copy 
1. 22
2. 9
3. -3
https://ideone.com/Uur412
language:
C++ (gcc 8.3)
created:
9 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!