OJ Board

thanks for explanations,math is international. what are the wights for the new graph ?
Weights stay the same. That is, if there is any rib a -> b, than in new graph each rib (a,x) -> (b,y) (of course, if the rib exists) will have the same weight.

well very nice imagination you have.
This idea ...

do u see any easier easy solution if the K =V.
That means to find a shortest path if the graph must pass through all the nodes of a complete graph .
a kind of shortest hamiltonian path ?

I asked this because the problem can be reduced to a hamiltonian path if
we construct a graph complete G1= (V1 ...

Ok.
Let's have a graph
1 -> 2, 2 -> 3, 3 -> 4, 1 -> 3, 2 -> 4
and the only marked vertex is 2.
So the problem is to find a path from 1 to 4 , visiting vertex 2.
Let's build new graph G' (a 'state graph'), in which each vertex is a pair (v,m), here m can take only two values: 0 or 1 (mask of length ...

I don't think it's a polynomial-solvable problem.
I suggest an O (M 2^K (logN + K)) algorithm (N - number of vertices, M - ribs, K - number of selected vertices). Let's make another graph, with N 2^K vertices, i.e. each vertex is a pair (original_vertex, visited_mask), what means that we stand in a ...

for the case |K| =1. there is an intersting discusion on topcoder:
http://forums.topcoder.com/?module=Thre ... rt=0&mc=24
but i not see how can be for the general case.

thank you so much for the time you took to look into the
term of the problem and to draw the solution.
sorry for my bad translation . It thought that arcs , tracks are part of the math heritage.
it seems that is not.
after i consulted with other big brains and i read more carefully the problem it ...

the corect text is


i have a problem and i have no idea of how to start.
there is a graph direct with weights that are real and a set of arcs F. A track is named "strained " related to F
if any arc (uv) from track is either in F
or there is no outgoing arc from u in set F.
given 2 vertexes ...

hi all
i have a problem and i have no idea of how to start.
there is a graph direct with weight in R and a set of lines S. a track is considered "strained " related with S if any line (uv) are
either in S or there is no outgoing line from u in set s . (
the algorithm should answer if there exist a ...

i'm thinking if we can find if there is at least one path going through a line.
my approach is to memorate all shortest path (if i use dijkstra ) in a arrays of paths
and check if the magic line is in the array.
u think it would work with negative edge ?

does anyone have other idea ?
thanks

not sure if is right. intuitively is like this. but think at a graph (complete)
and the MST . then we just have the choose the adiacente number in the sorted array but win min values.
are these equivalente ? same solution?