Solve the problem with code:Ack Country has discovered large quantities of crude oil under its territory. The king decided that all n industrial facilities in the country should be connected with crude oil to keep production working. There are two ways to supply crude oil to industrial facilities, either by laying pipelines to other industrial facilities that are already supplied with crude oil, or by exploring for oil at the plant site.The cost of crude oil exploration is w, and the cost of connecting two industrial facilities is c, given in matrix form, and the main diagonal of matrix is 0. Calculate the minimum cost of supplying crude oil to all industrial facilities.
时间: 2024-02-23 08:00:57 浏览: 78
Sure, here is a Python code that solves the problem using the Floyd-Warshall algorithm:
```python
INF = float('inf')
def find_min_cost(n, c, w):
for k in range(n):
for i in range(n):
for j in range(n):
c[i][j] = min(c[i][j], c[i][k] + c[k][j])
w[i][j] = min(w[i][j], c[i][j] + min(w[i][k], w[k][j]))
return sum(sum(row) for row in w)
n = int(input())
c = []
w = []
for i in range(n):
c_row = list(map(int, input().split()))
c.append(c_row)
w_row = [INF if x == 0 else x for x in c_row]
w.append(w_row)
print(find_min_cost(n, c, w))
```
This code takes the input of `n`, the size of the matrix, `c`, the cost of connecting two industrial facilities, and `w`, the cost of crude oil exploration. It then initializes the `INF` constant to represent infinity and sets the diagonal of `w` to infinity since exploration is not required for facilities that already have oil.
The algorithm then uses three nested loops to calculate the minimum cost of connecting all the facilities. It first calculates the shortest path between two facilities using the `c` matrix with the Floyd-Warshall algorithm. It then calculates the cost of supplying oil to each facility by adding the cost of connecting the facility to the nearest facility with oil and the cost of exploration if necessary.
Finally, the algorithm returns the total minimum cost of supplying oil to all facilities by summing up the values in the `w` matrix.
Please note that this code assumes that the input is valid and follows the problem statement. It also assumes that the input is formatted correctly.
阅读全文