Submission #533079


Source Code Expand

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
#define fst first
#define snd second
using namespace std;
typedef long long ll;
//#define int long long
template<class C>int size(const C &c){ return c.size(); }
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}

bool solve(){
    int n; cin >> n;
    vector<vector<ll>> a(n, vector<ll>(n));
    rep(i, n) rep(j, n) cin >> a[i][j];
    vector<vector<ll>> b(n, vector<ll>(n));
    const ll INF = 1LL<<55;
    rep(i, n) rep(j, n) b[i][j] = (a[i][j] == -1 ? INF : a[i][j]);
    rep(i, n) b[i][i] = 0;
    rep(k, n) rep(i, n) rep(j, n)
        chmin(b[i][j], b[i][k] + b[k][j]);
    bool ok = true;
    rep(i, n) rep(j, n) ok &= b[i][j] == (a[i][j] == -1 ? INF : a[i][j]);
    cout << (ok ? "YES" : "NO") << endl;
    return true;
}
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);
    int t; cin >> t;
    rep(_, t) solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s:

Submission Info

Submission Time
Task C - 最短経路
User MiSawa
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1490 Byte
Status AC
Exec Time 49 ms
Memory 1288 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 41
Set Name Test Cases
All 00_sample.txt, 10_random_00.txt, 10_random_01.txt, 10_random_02.txt, 10_random_03.txt, 10_random_04.txt, 10_random_05.txt, 10_random_06.txt, 10_random_07.txt, 10_random_08.txt, 10_random_09.txt, 10_random_10.txt, 10_random_11.txt, 10_random_12.txt, 10_random_13.txt, 10_random_14.txt, 10_random_15.txt, 10_random_16.txt, 10_random_17.txt, 10_random_18.txt, 10_random_19.txt, 10_random_20.txt, 10_random_21.txt, 10_random_22.txt, 10_random_23.txt, 10_random_24.txt, 10_random_25.txt, 10_random_26.txt, 10_random_27.txt, 10_random_28.txt, 10_random_29.txt, 22_random_30.txt, 22_random_31.txt, 23_coplete_32.txt, 23_coplete_33.txt, 24_path_34.txt, 24_path_35.txt, 25_tree_36.txt, 25_tree_37.txt, 26_noedge_38.txt, 27_dot_39.txt
Case Name Status Exec Time Memory
00_sample.txt AC 39 ms 1104 KB
10_random_00.txt AC 36 ms 1176 KB
10_random_01.txt AC 43 ms 1168 KB
10_random_02.txt AC 48 ms 1176 KB
10_random_03.txt AC 48 ms 1100 KB
10_random_04.txt AC 46 ms 1088 KB
10_random_05.txt AC 38 ms 1108 KB
10_random_06.txt AC 40 ms 1168 KB
10_random_07.txt AC 38 ms 1108 KB
10_random_08.txt AC 39 ms 1136 KB
10_random_09.txt AC 44 ms 1136 KB
10_random_10.txt AC 39 ms 1164 KB
10_random_11.txt AC 42 ms 1140 KB
10_random_12.txt AC 42 ms 1104 KB
10_random_13.txt AC 42 ms 1204 KB
10_random_14.txt AC 49 ms 1108 KB
10_random_15.txt AC 38 ms 1076 KB
10_random_16.txt AC 37 ms 1168 KB
10_random_17.txt AC 37 ms 1172 KB
10_random_18.txt AC 38 ms 1112 KB
10_random_19.txt AC 39 ms 1104 KB
10_random_20.txt AC 43 ms 1108 KB
10_random_21.txt AC 40 ms 1204 KB
10_random_22.txt AC 47 ms 1200 KB
10_random_23.txt AC 39 ms 1196 KB
10_random_24.txt AC 35 ms 1144 KB
10_random_25.txt AC 36 ms 1176 KB
10_random_26.txt AC 37 ms 1108 KB
10_random_27.txt AC 36 ms 1180 KB
10_random_28.txt AC 36 ms 1196 KB
10_random_29.txt AC 36 ms 1108 KB
22_random_30.txt AC 37 ms 1104 KB
22_random_31.txt AC 36 ms 1200 KB
23_coplete_32.txt AC 37 ms 1068 KB
23_coplete_33.txt AC 38 ms 1164 KB
24_path_34.txt AC 37 ms 1196 KB
24_path_35.txt AC 37 ms 1196 KB
25_tree_36.txt AC 37 ms 1196 KB
25_tree_37.txt AC 38 ms 1288 KB
26_noedge_38.txt AC 37 ms 1104 KB
27_dot_39.txt AC 31 ms 1072 KB