Submission #1691519
Source Code Expand
#include "bits/stdc++.h" using namespace std; const int N = 305; const int inf = 1e9 + 9; int n; int graph[N][N]; vector < pair < int , pair < int , int > > > v; unsigned dp[N][N]; long long ans; int main(){ scanf("%d" , &n); for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= n ; ++j){ scanf("%d" , &graph[i][j]); if(j > i){ v.push_back({graph[i][j] , {i , j}}); } dp[i][j] = inf; } dp[i][i] = 0; } sort(v.begin() , v.end()); for(auto it : v){ int a = it.second.first; int b = it.second.second; int c = it.first; if(dp[a][b] < c){ printf("-1\n"); return 0; } if(dp[a][b] == c){ continue; } ans += c; for(int i = 1 ; i <= n ; ++i){ for(int j = 1 ; j <= n ; ++j){ dp[i][j] = min(dp[i][j] , min(dp[i][a] + dp[b][j] , dp[i][b] + dp[a][j]) + c); } } } printf("%lld\n" , ans); }
Submission Info
Submission Time | |
---|---|
Task | D - Restoring Road Network |
User | rajat1603 |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 883 Byte |
Status | AC |
Exec Time | 212 ms |
Memory | 1656 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:11:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d" , &n); ^ ./Main.cpp:14:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d" , &graph[i][j]); ^
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 | 75 ms | 1656 KB |
02.txt | AC | 76 ms | 1656 KB |
03.txt | AC | 77 ms | 1656 KB |
04.txt | AC | 77 ms | 1656 KB |
05.txt | AC | 79 ms | 1656 KB |
06.txt | AC | 86 ms | 1656 KB |
07.txt | AC | 94 ms | 1656 KB |
08.txt | AC | 209 ms | 1656 KB |
09.txt | AC | 212 ms | 1656 KB |
10.txt | AC | 94 ms | 1656 KB |
11.txt | AC | 113 ms | 1656 KB |
12.txt | AC | 67 ms | 1656 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 |