**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

constraints?

easi task

Binary search for the answer plus BFS to check if it's possible. Details: think.

I've never heard of BFS on weighted graph ... how would that be done ?

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).

I used a combination of Dijkstra & DP and it worked. Thank You Xellos

Could you please post the question link? I would like to solve it too.

Thanks in advance :)