Help for this nice problems
Posted: Sat May 13, 2006 1:22 pm
I found this problems in some text which I get from my teachar. I tried to solve them but I failed.
1. You are given an oriented graph. Each edge of the graph is colored in one of the three colors. Problem is to find the length of the shortest path from the first vertex to the N-th. Note that any two successive edges in the path can't have the same color. Number of vertices of the graph is less than 200.
2. You are givewn a matrix A size mxn(1<=m<=n<=100) such that a(ij) is from the interval [-50, 50]. You need to chose exactly one number from every row such that if the chosen numbers are a(1, j(1)), a(2, j(2)), .. a(m, j(m)) then it is true that j(1)< j(2)< j(3)< ... < j(m). Problem is to minimize the sum of the chosen numbers.
Time limit for both problems is 0.25sec.
Sorry for my english.
1. You are given an oriented graph. Each edge of the graph is colored in one of the three colors. Problem is to find the length of the shortest path from the first vertex to the N-th. Note that any two successive edges in the path can't have the same color. Number of vertices of the graph is less than 200.
2. You are givewn a matrix A size mxn(1<=m<=n<=100) such that a(ij) is from the interval [-50, 50]. You need to chose exactly one number from every row such that if the chosen numbers are a(1, j(1)), a(2, j(2)), .. a(m, j(m)) then it is true that j(1)< j(2)< j(3)< ... < j(m). Problem is to minimize the sum of the chosen numbers.
Time limit for both problems is 0.25sec.
Sorry for my english.