TTRIP - Tham quan Thành Cổ

Tác giả: ll931110

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int n,a[105][105];
int INF = (1 << 30) - 5;
bool check[105];

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      scanf("%d", &a[i][j]);
      if (i != j && !a[i][j]) a[i][j] = INF;
    }
    
   for (int k = 0; k < n; k++)
     for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++)
         a[i][j] = min(a[i][j],a[i][k] + a[k][j]);
   
   int ret = 0,start = 0;
   for (int iter = 0; iter < n - 2; iter++) {
     int len = INF,pos;
     for (int j = 1; j < n - 1; j++) if (!check[j] && a[start][j] < len) {
       len = a[start][j];
       pos = j;
     }
     ret += len;
     check[pos] = true;
     start = pos;
   }
   printf("%d\n", ret + a[start][n - 1]);
}

Download