#include <iostream> #include <cassert> using namespace std; typedef long long LL; const int MAXN = (1<<11)-1; const int OO = (1<<30)-1; int c[MAXN][MAXN]; int main() { int n; assert(1 == scanf("%d", &n)); LL result = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j <= n; ++j) { assert(1 == scanf("%d", &c[i][j])); } } for (int i = 0; i < n; ++i) { int k = i; c[i][i] = OO; for (int j = i + 1; j <= n; ++j) { if (c[i][j] < c[i][k]) { k = j; } } result += c[i][k]; for (int j = i + 1; j <= n; ++j) { if (j < k) { c[j][k] = min(c[j][k], c[i][j]); } if (j > k) { c[k][j] = min(c[k][j], c[i][j]); } } } printf("%lld\n", result); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream> #include <cassert> using namespace std; typedef long long LL; const int MAXN = (1<<11)-1; const int OO = (1<<30)-1; int c[MAXN][MAXN]; int main() { int n; assert(1 == scanf("%d", &n)); LL result = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j <= n; ++j) { assert(1 == scanf("%d", &c[i][j])); } } for (int i = 0; i < n; ++i) { int k = i; c[i][i] = OO; for (int j = i + 1; j <= n; ++j) { if (c[i][j] < c[i][k]) { k = j; } } result += c[i][k]; for (int j = i + 1; j <= n; ++j) { if (j < k) { c[j][k] = min(c[j][k], c[i][j]); } if (j > k) { c[k][j] = min(c[k][j], c[i][j]); } } } printf("%lld\n", result); return 0; } |