One day when I had my math class,I came up with an idea.But I found that I can't solve it.↵
↵
After class I asked many people but they did't solve it too.↵
↵
Here's the problem:↵
↵
You are given a undirected weighted graph with n nodes and m edges.↵
↵
You need to find a simple path from 1 to n to maximize the maximum value of edges in the path minus the minimum one.↵
↵
A simple path means that you can't pass through one edge twice or more.↵
↵
(I don't know how large n,m can be)↵
↵
Update:Thanks to [user:TimonKnigge,2019-07-12],we can solve it in $O(m^3)$
↵
After class I asked many people but they did't solve it too.↵
↵
Here's the problem:↵
↵
You are given a undirected weighted graph with n nodes and m edges.↵
↵
You need to find a simple path from 1 to n to maximize the maximum value of edges in the path minus the minimum one.↵
↵
A simple path means that you can't pass through one edge twice or more.↵
↵
(I don't know how large n,m can be)↵
↵
Update:Thanks to [user:TimonKnigge,2019-07-12],we can solve it in $O(m^3)$