Submission #1275821
Source Code Expand
#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; for(int i=0;i<t;i++){ int n; cin>>n; vector<vector<int>> edge(n,vector<int>(n,-1)); vector<vector<int>> a(n,vector<int>(n)); const int INF=1e8; vector<vector<int>> dp(n,vector<int>(n,INF)); bool isok=true; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>a[i][j]; if(a[i][j]!=-1) dp[i][j]=a[i][j]; if(a[i][j]!=0 && i==j) isok=false; } } for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(dp[i][j]==INF && a[i][j]==-1 || a[i][j]==dp[i][j]){ continue; } else{ isok=false; } } } cout<<(isok ? "YES" : "NO")<<endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - 東京都 |
User | nikutto |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1160 Byte |
Status | WA |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 0 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 10_random_to_kyo.txt, 20_noised_tokyoto.txt, 99_teuchi.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
10_random_to_kyo.txt | WA | 1 ms | 256 KB |
20_noised_tokyoto.txt | WA | 1 ms | 256 KB |
99_teuchi.txt | WA | 1 ms | 256 KB |