Submission #1696378
Source Code Expand
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
# define INF 0x3f3f3f3f
template <typename T>
struct Edge {
int src, dst;
T weight;
Edge(int src, int dst, T weight) :
src(src), dst(dst), weight(weight) { }
};
template <typename T>
bool operator < (const Edge<T> &e, const Edge<T> &f) {
return e.weight != f.weight ? e.weight > f.weight :
e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
template <typename T>
struct Graph {
int V; // 頂点数
vector<Edge<T>> *adj;
bool directed;
explicit Graph(int V, bool directed) {
this->V = V;
this->adj = new vector<Edge<T>> [V];
this->directed = directed;
}
// 辺を追加
void add_edge(int src, int dst, T weight) {
assert(src >= 0 && src < V);
assert(dst >= 0 && dst < V);
adj[src].push_back(Edge<T>(src, dst, weight));
if (!directed) {
adj[dst].push_back(Edge<T>(dst, src, weight));
}
}
// 辺があるかチェック
bool has_edge(int src, int dst) {
return any_of(adj[src].begin(), adj[src].end(),
[dst](Edge<T> e) { return e.dst == dst; });
}
// 辺の重みをチェック
T get_weight(int src, int dst) {
for (const auto &e : adj[src]) {
if (e.dst == dst) {
return e.weight;
}
}
return INF;
}
ll get_total_weights() {
ll result = 0;
for (int i = 0; i < V; i++) {
for (const auto &e : adj[i]) {
result += e.weight;
}
}
return result;
}
// 辺を削除
void remove_edge(int src, int dst) {
adj[src].erase(remove_if(adj[src].begin(), adj[src].end(),
[dst](Edge<T> e) { return e.dst == dst; }),
adj[src].end());
if (!directed) {
adj[dst].erase(remove_if(adj[dst].begin(), adj[dst].end(),
[src](Edge<T> e) { return e.dst == src; }),
adj[dst].end());
}
}
// 連結判定
bool is_connected() {
vector<bool> visited(V, false);
queue<int> container;
container.push(0);
while (!container.empty()) {
int p = container.front();
container.pop();
visited[p] = true;
for (const auto &e : adj[p]) {
if (!visited[e.dst]) {
container.push(e.dst);
}
}
}
return all_of(visited.begin(), visited.end(),
[](bool v) { return v; });
}
// 二部グラフ判定
bool is_bipartite() {
vector<int> visited(V, -1);
queue<int> container;
container.push(0);
visited[0] = 1;
while (!container.empty()) {
int p = container.front();
container.pop();
for (const auto &e : adj[p]) {
if (visited[e.dst] == -1) {
visited[e.dst] = (visited[p] + 1) % 2;
container.push(e.dst);
} else if (visited[e.dst] == visited[p]) {
return false;
}
}
}
// 連結でない場合は false
return all_of(visited.begin(), visited.end(),
[](int v) { return v >= 0; });
}
// vector<T> shortest_path(int s);
// vector<vector<T>> shortest_paths();
// Graph<T> spanning_tree();
};
int dist[310][310] = {};
int dp[310][310] = {};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> dist[i][j];
dp[i][j] = dist[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (k == i || k == j || i == j || dp[j][i] == INF || dp[i][k] == INF) continue;
int mi = dp[j][i] + dp[i][k];
if (dist[j][k] > mi) {
cout << -1 << endl;
return 0;
} else if (dist[j][k] == mi) {
dp[j][k] = INF;
}
// dist[j][k] = min(dist[j][k], mi);
}
}
}
ll total = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (dp[i][j] != INF) {
total += dp[i][j];
}
}
}
cout << total / 2 << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Restoring Road Network |
User |
sinhrks |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
4592 Byte |
Status |
AC |
Exec Time |
67 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 |
48 ms |
1024 KB |
02.txt |
AC |
48 ms |
1024 KB |
03.txt |
AC |
50 ms |
1024 KB |
04.txt |
AC |
51 ms |
1024 KB |
05.txt |
AC |
53 ms |
1024 KB |
06.txt |
AC |
67 ms |
1024 KB |
07.txt |
AC |
9 ms |
1024 KB |
08.txt |
AC |
52 ms |
1024 KB |
09.txt |
AC |
53 ms |
1024 KB |
10.txt |
AC |
9 ms |
1024 KB |
11.txt |
AC |
9 ms |
1024 KB |
12.txt |
AC |
10 ms |
1024 KB |
13.txt |
AC |
1 ms |
256 KB |
subtask0_0.txt |
AC |
1 ms |
256 KB |
subtask0_1.txt |
AC |
1 ms |
256 KB |
subtask0_2.txt |
AC |
1 ms |
256 KB |
subtask0_3.txt |
AC |
1 ms |
256 KB |