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
WA × 3
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