A problem I can't solve
Difference between en4 and en5, changed 92 character(s)
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)$↵

Update:Thanks to [user:aleex,2019-07-13],we can solve it in $O(m\log m\log \max value
2 \times n^3)$

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English sys. 2019-07-14 06:16:40 92
en4 English sys. 2019-07-13 11:43:16 91 Tiny change: 'logmlogmax_Value)$' -> 'logmlogmaxValue)$'
en3 English sys. 2019-07-12 19:42:35 76
en2 English sys. 2019-07-12 10:30:49 5 Tiny change: 'n to maximum the maxim' -> 'n to maximize the maxim'
en1 English sys. 2019-07-12 10:30:23 506 Initial revision (published)