I Found A Data in D in the 576 Contest that Could Cause Many People to Make Mistakes.
Difference between en1 and en2, changed 21 character(s)
The solution has been given, but for a better explanation, repeat it here:↵
There are <=m different graphs, sorting the weights from small to large, and adding the edges of equal edge weights to each side.↵

First, we can find out what is the adjacency matrix of the s[now].c step by using the previous edge set, and ensure that there is no n before.↵

Now you can continue to go s[now+1].c-s[now].c on the current map and see if you have seen n in the process.↵
Maintain an adjacency matrix G[i] equal to 1+E+E^2+...+E^{2^i}, where addition represents or, multiplication represents the adjacency matrix transition, and E is the current edge set.↵

The processing method of G[i] can consider G[0]=1+E, G[i]=G[i-1]^2 (i>=1)↵

If G[i] is present, so that the adjacency matrix (P*G[i]) can go from 1 to n, then we can go from 1 to n from the current graph.↵

Of course, there is still uncertainty. We need to know the answer accurately. Multiply it. If *G[i] can't make the adjacency matrix go from 1 to n, multiply E^{2^i} because It can be guaranteed that multiplying by 1, E, ..., E^{2^i} can not make the adjacency matrix go from 1 to n, and finally add 1 to it, and the proof must be satisfied.↵

If it does not exist or exists but the minimum number of steps required >s[now+1].c-s[now].c, then the answer still needs to go up 
and downto the next graph to check if there is a better answer.↵

But if you don't judge whether it exists or not, but you need the minimum number of steps >s[now+1].c-s[now].c, you can still pass this question.↵

Here is a set of data to help you detect if your code is really correct:↵

**8 8**↵

**1 2 0**↵

**2 3 0**↵

**3 4 0**↵

**4 5 0**↵

**5 6 0**↵

**6 7 0**↵

**7 8 0**↵

**6 8 5**↵
 ↵
_Right Answer:6_↵

_Simple Answer:7_↵


Finally, paste my blog [link](https://blog.csdn.net/deep_kevin)↵

Interested friends can find more interesting things in the blog.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Deep_Kevin 2019-11-14 08:19:12 21 Tiny change: ' to go up and down to check ' -> ' to go up to the next graph to check '
en1 English Deep_Kevin 2019-11-14 05:59:58 1986 Initial revision (published)