fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.   int t,n,m,cnt,cnt1,flag,time=0;
  7.   short int **res;
  8.   unsigned long int **st;
  9.   unsigned long int b;
  10.  
  11.   cin>>t;
  12.   cnt=t;
  13.   res=new short int*[t];
  14.  
  15.   while(t)
  16.   {
  17.     cnt1=0;
  18.     time=0;
  19.  
  20.     cin>>n;
  21.     cin>>m;
  22.     cin>>b;
  23.  
  24. 	res[cnt-t]=new short int[m+1];
  25.  
  26.     //allocation
  27.     st=new unsigned long int*[m];
  28.     for(int i=0;i<m;i++)
  29.     {
  30.       st[i]=new unsigned long int[4];
  31.     }
  32.  
  33.     for(int i=0;i<m;i++)
  34.     {
  35.       cin>>st[i][0];
  36.       cin>>st[i][1];
  37.       cin>>st[i][2];
  38.       st[i][3]=0;
  39.     }
  40.  
  41.     unsigned long int min;
  42.     int dest=0,minj=-1;
  43.  
  44.  
  45.     for(int i=0;i<m && time<b;i++)
  46.     {
  47.       min=1000000001;
  48.       for(int j=0;j<m;j++)
  49.       {
  50. 		 if(st[j][0]==dest && min>st[j][2] && !st[j][3])
  51. 		 {
  52. 		   min=st[j][2];
  53. 		   minj=j;
  54. 		 }
  55.       }
  56.       st[minj][3]=1;
  57.       flag=1;
  58.       for(int k=0;k<cnt1;k++)
  59.       {
  60. 		if(res[cnt-t][k]==st[minj][1])
  61. 		{
  62. 		  flag=0;
  63. 		}
  64.       }
  65.  
  66.       if(flag)
  67.       {
  68. 		res[cnt-t][cnt1++]=st[minj][1];
  69.       }
  70.  
  71.       dest=st[minj][1];
  72.       time+=min;
  73.     }
  74.  
  75.     res[cnt-t][cnt1]=-1;
  76.  
  77.     //deallocation
  78.     for(int i=0;i<m;i++)
  79.     {
  80.       delete [] st[i];
  81.     }
  82.     delete [] st;
  83.  
  84.     t--;
  85.   }
  86.  
  87.   int j;
  88.   for(int i=0;i<cnt;i++)
  89.   {
  90.     j=0;
  91.     while(res[i][j]!=-1)
  92.     {
  93.       cout<<res[i][j++]<<" ";
  94.     }
  95.     cout<<"-1";
  96.     cout<<"\n";
  97.   }
  98.  
  99.   for(int i=0;i<cnt;i++)
  100.   {
  101.      delete [] res[i];
  102.   }
  103.   delete [] res;
  104.  
  105.   return 0;
  106. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
2
3 4 2
0 1 1
0 2 1
1 2 1
2 1 2
5 7 11
0 1 2
1 0 3
0 2 1
2 3 2
3 2 3
2 4 1
4 2 2
stdout
copy 
1 2 -1
2 4 3 -1
https://ideone.com/9D0nQo
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!