### Dalisyron's blog

By Dalisyron, history, 7 years ago,

Problem :

Given a weighted directed graph with both negative and positive edges, Find a path from vertex 1 to n, in which minimum subpath weight(starting from vertex 1) is maximum.

I can't think of any graph algorithm that can help me solve this problem, so any suggestions are appreciated.

N<=500

• -1

 » 7 years ago, # |   +6 constraints?
 » 7 years ago, # |   -14 easi task
 » 7 years ago, # |   +7 Binary search for the answer plus BFS to check if it's possible. Details: think.
•  » » 7 years ago, # ^ |   +9 I've never heard of BFS on weighted graph ... how would that be done ?
•  » » » 7 years ago, # ^ |   0 I parsed "subpath" as "edge"...If they're paths from vertex 1, it's modified Dijkstra (you only have to ignore possible paths with length < checked answer).
•  » » » » 7 years ago, # ^ |   0 I used a combination of Dijkstra & DP and it worked. Thank You Xellos
 » 7 years ago, # |   +1 Could you please post the question link? I would like to solve it too.Thanks in advance :)