srm622D1E.cpp

// {{{ $VIMCODER$ <--------
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <cmath>
#include <queue>
#include <unordered_map>
#include <numeric>
#include <set>
#include <cstring>
using namespace std;
// }}}

class BuildingRoutes {
public:
	int build(vector <string> dist, int T) {
		vector<vector<int>> d(dist.size(),vector<int>(dist.size()));
		for (int i = 0; i < dist.size(); i++)
			for (int j = 0; j < dist.size(); j++)
				d[i][j] = dist[i][j]-'0';
		for (int k = 0; k < d.size(); k++)
			for (int i = 0; i < d.size(); i++)
				for (int j = 0; j < d.size(); j++)
					d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
		int res = 0;
		for (int i = 0; i < d.size(); i++) {
			for (int j = 0; j < d.size(); j++) {
				if(i == j) continue;
				int cnt = 0;
				for (int k = 0; k < d.size(); k++) {
					for (int l = 0; l < d.size(); l++)
						if(k != l && d[k][i]+dist[i][j]-'0'+d[j][l] == d[k][l]) ++cnt;
				}
				if(cnt >= T) res += dist[i][j]-'0';
			}
		}
		return int(res);
	}
};