#include <stdio.h> int dir[100][100]; int mtx[100][100]; int path[100]; int main() { int a, b, c, min; int i, j, row, col, a_dir, c_dir; while (scanf("%d %d",&row,&col)==2) { for (i=1 ; i<=row ; i++) for (j=1 ; j<=col ; j++) scanf("%d",&mtx[i][j]); for (j=col-1 ; j>=1 ; j--) { for (i=1 ; i<=row ; i++) { if (i-1<1) { a_dir = -1; a = mtx[i][j] + mtx[row][j+1]; } else { a_dir = 0; a = mtx[i][j] + mtx[i-1][j+1]; } if (i+1>row) { c_dir = -1; c = mtx[i][j] + mtx[1][j+1]; } else { c_dir = 0; c = mtx[i][j] + mtx[i+1][j+1]; } b = mtx[i][j] + mtx[i][j+1]; if (a<=b && a<=c) { mtx[i][j] = a; if (a_dir<0) { if (a==b) { dir[i][j] = i; } else if (a==c) { dir[i][j] = i+1; } else { dir[i][j] = row; } } else { if (a==c && c_dir<0) dir[i][j] = 1; else dir[i][j] = i-1; } } else if (b<=a && b<=c) { mtx[i][j] = b; if (b==a) { if (a_dir<0) { dir[i][j] = i; } else { dir[i][j] = i-1; } } else if (b==c) { if (c_dir<0) { dir[i][j]=1; } else { dir[i][j]=i; } } else { dir[i][j] = i; } } else if (c<=a && c<=b) { mtx[i][j] = c; if (c_dir<0) { dir[i][j] = 1; } else { if (c==a) { dir[i][j]=i-1; } else if (c==b) { dir[i][j]=i; } else { dir[i][j]=i+1; } } } } } for (i=1, min=mtx[1][1], path[1]=1 ; i<=row ; i++) { if (mtx[i][1]<min) { min = mtx[i][1]; path[1] = i; } } printf("%d",path[1]); for (j=2 ; j<=col ; j++) { path[j] = dir[path[j-1]][j-1]; printf(" %d",path[j]); } printf("\n%d\n",min); } return 0; }
Sunday, December 04, 2011
[UVa] 116 - Unidirectional TSP
Subscribe to:
Post Comments (Atom)
Connect Rapoo MT750S with Linux (Tested on Manjaro)
I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_hKnRuzMZ7uZ74xzkMZ5s6jMIRkK-FU8XXxLOGIXx_gAs7gVeDzeZ_3tZZhAiTF7gta-EcR34pwaR06bMvLJKJXiAwJj2A1l_k068J61zm_ZDqPITGCMxFPlI3cWqhOY1q_aHtA/s320/Rapoo-MT550-Smart-4.jpg)
-
I like coding a lot, keeps me glued to the PC for hours. For that reason it's a need to edit the Syntax Highlighter to suit my eyes for...
-
I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...
-
I will be super quick about this. I received it today and upon connecting on my Manjaro box, it showed by Wifi but with very poor signal. I...
No comments:
Post a Comment
Post your comment here. If you want to say something about programming problems, scripts, software etc, please try to be as descriptive as possible.