#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define MAXR 10
#define MAXC 100
using namespace std;
int main()
{
int m,n;//row column
int array[MAXR][MAXC],mini[MAXR][MAXC],child[MAXR][MAXC];//entry,minimum sum, path
while(cin>>m>>n){if(feof(stdin))break;
int i,j;//iterator
for(i=0;i<m;i++)
for(j=0;j<n;j++)cin>>array[i][j]; //array entry
for(i=0;i<m;i++){mini[i][n-1]=array[i][n-1];}
for(j=n-2;j>=0;j--) //dp apply +child set
for(i=0;i<m;i++)
{
mini[i][j]=mini[(m+i-1)%m][j+1];
child[i][j]=(m+i-1)%m;
if(mini[i][j]>mini[i][j+1]){mini[i][j]=mini[i][j+1];
child[i][j]=i;
}
else if(mini[i][j]==mini[i][j+1] && child[i][j]>i)child[i][j]=i;
if(mini[i][j]>mini[(m+i+1)%m][j+1])
{mini[i][j]=mini[(m+i+1)%m][j+1];
child[i][j]=(m+i+1)%m;
}
else if(mini[i][j]==mini[(m+i+1)%m][j+1] && child[i][j]>(m+i+1)%m)
child[i][j]=(m+i+1)%m;
mini[i][j]+=array[i][j];
}
int minimum=30000000,minirow;
for(i=0;i<m;i++)if(minimum>mini[i][0]){minimum=mini[i][0];
minirow=i;
} //minimum sum and source find
vector<int>path;
bool blank =false;
for(j=0;j<n;j++){path.push_back(minirow+1); //path ready+print
if(blank)cout<<" ";
cout<<path[j];
minirow=child[minirow][j];
blank=true;
}
cout<<endl;
cout<<minimum<<endl;
}
return 0;
}
এই মন্তব্যটি লেখক দ্বারা সরানো হয়েছে।
উত্তরমুছুনI have tried all testcase found in online judge forum but still wrong answer.
উত্তরমুছুনHere is my code
#include
#include
#include
#include
long long tsp[10][100];
int path[10][100], row, col;
int main()
{
long long mini;
int in[3]={-1,0,1},r,mr,c;
while(scanf("%d %d", &row, &col)!=EOF)
{
for(int i=0;i=0;--j) // last dik thk start krbo
{
for(int i=0;i tsp[i][j]+ tsp[r][j+1] )
{
mini=tsp[i][j]+ tsp[r][j+1];
mr=r;
path[i][j]=mr;
}
else if(mini == (tsp[i][j]+ tsp[r][j+1]) )
{
mr=std::min(mr,r);
path[i][j]=mr;
}
}
tsp[i][j]=mini;
}
}
mini = tsp[0][0];
std::string s,t;
r=0;c=0;
s.clear();
s+= r+1+48;
while(path[r][c]!=-1)
{
r=path[r][c];
s+= r+1+48;
++c;
}
for(int i=1;i tsp[i][0])
{
mini= tsp[i][0];
r=i;c=0;
s.clear();
s+= r+1+48;
//p.push(r);
while(path[r][c]!=-1)
{
r=path[r][c];
s+= r+1+48;
++c;
}
}
/*else if(mini== tsp[i][0])
{
r = i;c = 0;
t.clear();
t+= r+1+48;
while(path[r][c] != -1)
{
r=path[r][c];
t+= r+1+48;
++c;
}
if(s.compare(t) > 0) s = t;
}
*/
}
int len=s.size();
printf("%c", s[0]);
for(int i=1;i<len;++i)
{
printf(" %c", s[i]);
}
puts("");
printf("%lld\n", mini);
}
return 0;
}