Submission #1602625
Source Code Expand
#include <bits/stdc++.h>
//#include <boost/functional/hash.hpp>
//example: unordered_set< pair<int,int>,boost::hash< std::pair<int, int> > > used;
//priority_queue< pair<int,pair<int,int> >, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int> > > > pqueue; //cost, vertex(行き先)
using namespace std;
#define MODULE 1000000007
#define MP make_pair
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<class T, class U>
inline void chmin(T &t, U f) { if (t > f)t = f; }
template<class T, class U>
inline void chmax(T &t, U f) { if (t < f)t = f; }
template<typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val) { //usage: int dp[10][10]; Fill(dp,INF);
std::fill((T *) array, (T *) (array + N), val);
}
typedef pair<int, int> P;
typedef long long LL;
const int INF = INT_MAX / 2; //int_max->2*e+9 LLの時はLLONG_MAX
/*const int MAXN = 100001;
struct edge {
edge(int to, int cost) : to(to), cost(cost) {}
int to, cost;
};
vector<edge> graph[MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};*/
//-----Template---------
#define V 301
int a[V][V];
int test[V][V];
int n;
LL sumCost=0;
int mincost[V];
bool used[V];
void warshallFloid(){
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
test[i][j]=min(test[i][j],test[i][k]+test[k][j]);
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false); //cout<< fixed << setprecision(10);
cin >> n;
Fill(a, 0);
Fill(test, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; ++j) {
cin >>a[i][j];
sumCost+=a[i][j];
test[i][j] = a[i][j];
}
}
sumCost/=2;
warshallFloid();
bool flag = true;
for (int i = 0; i < n; ++i) {//2.7*10^6
for (int j = 0; j < n; ++j) {
if(a[i][j] != test[i][j]){
flag=false;
}
}
}
if(flag){
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
for (int k = 0; k < n; ++k) {
if( k==i || k==j )continue;
if(test[i][j]==(test[i][k]+test[k][j])){
sumCost-=test[i][j];
break;
}
}
}
}
cout<<sumCost<<endl;
}else{
cout<<-1<<endl;
}
}
Submission Info
Submission Time |
|
Task |
D - Restoring Road Network |
User |
yoyoyousei |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
2554 Byte |
Status |
AC |
Exec Time |
53 ms |
Memory |
1024 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
41 ms |
1024 KB |
02.txt |
AC |
41 ms |
1024 KB |
03.txt |
AC |
42 ms |
1024 KB |
04.txt |
AC |
43 ms |
1024 KB |
05.txt |
AC |
44 ms |
1024 KB |
06.txt |
AC |
53 ms |
1024 KB |
07.txt |
AC |
39 ms |
1024 KB |
08.txt |
AC |
43 ms |
1024 KB |
09.txt |
AC |
43 ms |
1024 KB |
10.txt |
AC |
39 ms |
1024 KB |
11.txt |
AC |
39 ms |
1024 KB |
12.txt |
AC |
40 ms |
1024 KB |
13.txt |
AC |
2 ms |
1024 KB |
subtask0_0.txt |
AC |
2 ms |
1024 KB |
subtask0_1.txt |
AC |
2 ms |
1024 KB |
subtask0_2.txt |
AC |
2 ms |
1024 KB |
subtask0_3.txt |
AC |
2 ms |
1024 KB |