Una pregunta de la Olimpiada de Informática requiere un proceso detallado y puntos extra. La respuesta debe darse hoy. ¡No se otorgarán puntos si llega tarde!

En realidad, este es el problema de circuito más corto de fuente única más estándar y existe un método extremadamente simple. Digámoslo de esta manera, el algoritmo floyed primero lee la matriz de adyacencia g (i, j). La distancia desde el sitio i-ésimo al sitio j-ésimo, la distancia no conectada se establece en un número muy grande, como 0xffffffffff. Por supuesto, también debe tenerse en cuenta que, dado que el camino es de dos vías, g (j, i) = g (i, j) Una vez completado el trabajo de preparación, es hora de comenzar con dp. El código aquí es demasiado simple. . Se recomienda memorizarlo

para ( k = 1; k <= n; k++ )

para ( i = 1; i <= n; i++ )

{

si ( i == k ) continuar

para ( j = 1; j <= n; j++ )

{

if ( j == i || j == k ) continuar

if ( g[ i ][ k ] + g[ k ][ j ] < g[ i ] [ j ] )

g[ i ][ j ] = g[ i ][ k ] + g[ k ][ j ];

}

}

}

} Esta ecuación es más problemática, así que no entraré en ella. La complejidad es O (n ^ 3) y el resultado final del circuito más corto. es g[ 1 ][ n ]. Si desea minimizar la cantidad de autobuses, debe cambiar el peso de todos los lugares excepto los no conectados a 1 y luego flotarlo una vez.

Lo siento, no me di cuenta - -

En este caso, se puede construir un nuevo gráfico

Considere cada línea de autobús como un nodo, conecte las líneas de autobús que se cruzan en un borde, y este borde conecta el punto de partida y la línea que pasa por el punto inicial (tenga en cuenta que el peso es 1), el punto final y la línea que pasa por el punto final (tenga en cuenta que el peso es 0), el peso de las dos líneas de autobús que se cruzan se establece en 1, para que pueda continúa con el siguiente paso