2017-ACM南宁网络赛
In this problem, we will define a graph called star graph, and the question is to find the minimum distance between two given nodes in the star graph.
Given an integer nnn, an n−dimensionaln-dimensionaln−dimensional star graph, also referred to as SnS_{n}Sn, is an undirected graph consisting of n!n!n! nodes (or vertices) and ((n−1) ∗ n!)/2((n-1) * n!)/2((n−1) ∗ n!)/2 edges. Each node is uniquely assigned a label x1 x2 ... xnx_{1} x_{2} ... x_{n}x1 x2 ... xn which is any permutation of the n digits 1,2,3,...,n{1, 2, 3, ..., n}1,2,3,...,n. For instance, an S4S_{4}S4 has the following 24 nodes 1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321{1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321}1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4