wip

79. Space Station Employment

Time Limit: 1 seconds

Memory Limit: 1024 MB

Rating: 1200

The Galactic Federation is constructing a new network of space stations across different planets in the Andromeda galaxy. Each space station requires a specialized crew to operate efficiently. The federation has identified $N$ space stations and $N$ specialized crews. Each crew is trained to handle specific tasks that are unique to each station. The goal is to assign one crew to each space station such that the total operational cost is minimized. You are given a cost array $C$ of size $N \cdot N$, where $C_{i,j}$ represents the cost of assigning crew $i$ to space station $j$. Your task is to find an assignment of crews to space stations such that each crew is assigned to exactly one space station, and the total assignment cost is minimized.

The first line contains an integer $N$, representing the number of space stations and crews. The next $N$ lines each contain $N$ integers. The $j$-th integer of the $i$-th line represents $C_{i,j}$, the cost of assigning crew i to space station $j$. $1 ≤ N ≤ 10$ $0 ≤ C_{i,j} ≤ 10^2$

Output a single integer, the minimum total cost of assigning all crews to all space stations.

Sample Input 0:
3
1 2 3
2 1 2
1 1 4

Sample Output 0:
4


Sample Input 1:
4
1 2 3 4
3 2 1 3
1 0 0 0
1 6 7 8

Sample Output 1:
4

For sample case 0, the most optimal choice whould be choosing C[0][0] (1), C[2][1] (1), C[1][2] (2)

KL Coding Cup October 2024 > Problem 17