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 upand 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.
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
↵
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.
