【題解】ZeroJudge f606: 2. 流量

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=f606

#include <iostream>
#include <cstring>
using namespace std;

int main() {
	int N, M, K;
	cin >> N >> M >> K;
	int Q[N][M];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> Q[i][j];
		}
	}
	int cost[K];
	memset(cost, 0, sizeof(cost));
	for (int k = 0; k < K; k++) {
		cost[k] = 0;
	}
	
	for (int k = 0; k < K; k++) {
		int c[N];
		for (int i = 0; i < N; i++) {
			cin >> c[i];
		}
		int traffic[M][M];
		memset(traffic, 0, sizeof(traffic));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				traffic[c[i]][j] += Q[i][j];
			}
		}
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				if (i == j) {
					cost[k] += traffic[i][j];
				} else {
					if (traffic[i][j] <= 1000) {
						cost[k] += traffic[i][j] * 3;
					} else {
						cost[k] += 1000 * 3;
	                    cost[k] += (traffic[i][j] - 1000) * 2;
					}
				}
			}
		}
	}
	int mn = 1e9;
	for (int i = 0; i < K; i++) {
		mn = min(mn, cost[i]);
	}
	cout << mn << "\n";
	return 0;
}

Python code (credit: Amy Chou)

N, M, K = map(int, input().split())
Q = []
for _ in range(N):
    Q.append(list(map(int, input().split())))
    
cost = [0 for _ in range(K)]
for k in range(K):
    c = list(map(int, input().split()))
    traffic = [[0 for i in range(M)] for j in range(M)]
    for i in range(N):
        for j in range(M):
            traffic[c[i]][j] += Q[i][j]
            
    for i in range(M):
        for j in range(M):
            if i == j:
                cost[k] += traffic[i][j]
            else:
                if traffic[i][j] <= 1000:
                    cost[k] += traffic[i][j] * 3
                else:
                    cost[k] += 1000 * 3
                    cost[k] += (traffic[i][j] - 1000) * 2
                    
print(min(cost))
            
分享本文 Share with friends