作者Dick901 (Sword)
看板ACMCLUB
標題[問題] uva 116 Unidirectional TSP 找不出錯誤
時間Wed Oct 13 21:33:41 2010
這一題，我在uva上judge都是wrong answer，但是在zerojudge上卻是accept answer，
我知道zerojudge的測資比較弱，但是我用了網路上Mat大大給的測資試，沒有問題啊！
可否請大大們幫我看看有沒有哪裡有bug！謝謝！
my code:
===========================================================
#include <stdio.h>
int M[20][110];
int dp[20][110];
int pa[20][110];
int main()
{
int m,n,i,j,k,min,thr[3];//thr陣列用來判斷上中下，請見下一個注釋
while(scanf("%d%d",&m,&n)!=EOF)
{
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&M[i][j]);
}
}
for(i=0;i<m;i++)
dp[i][n-1]=M[i][n-1];
for(i=n-2;i>=0;i--)
{
for(j=0;j<m;j++)
{
if(j==0) //這個if用來判斷前一行與他相鄰的三個dp
{ //陣列元素的上下位置，因為題目要求按照字典序，
thr[0]=j; //我的方法比較笨，請各位諒解！
thr[1]=j+1;
thr[2]=(j-1+m)%m;
}else if(j==m-1){
thr[0]=(j+1+m)%m;
thr[1]=j-1;
thr[2]=j;
}else{
thr[0]=j-1;
thr[1]=j;
thr[2]=j+1;
}
min=dp[thr[0]][i+1];
pa[j][i]=thr[0];
for(k=1;k<3;k++)
{
if(min>dp[thr[k]][i+1])
{
min=dp[thr[k]][i+1];
pa[j][i]=thr[k];
}
}
dp[j][i]=min+M[j][i];
}
}
min=dp[0][0];
int ps=0;
for(i=1;i<m;i++)
{
if(min > dp[i][0])
{
min=dp[i][0];
ps=i;
}
}
for(i=0;i<n-1;i++)
{
printf("%d ",ps+1);
ps=pa[ps][i];
}
printf("%d\n",ps+1);
printf("%d\n",min);
}
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.60.107.236