AtCoder Regular Contest 083

Submission #1597702

Source codeソースコード

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
typedef long long int ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<signed(n);i++)
#define EREP(i,n) for(int i=1;i<=signed(n);i++)
#define ALL(a) (a).begin(),(a).end()
using std::cout;
using std::vector;
using std::endl;
using std::cin;
using std::string;
//#define EVEL 1
#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const ll INF = 50000000000000000;
typedef std::pair<int,int> P;
struct edge {int to,cost;};
#define VMAX 301
    int N;
    ll d[VMAX][VMAX];
    ll A[VMAX][VMAX];
    bool vis[VMAX][VMAX]={};
    ll ans=0;
    bool No=false;
    void warshall_floyd(int n) { // nは頂点数
      for (int i = 0; i < n; i++)      // 経由する頂点
        for (int j = 0; j < n; j++)    // 開始頂点
          for (int k = 0; k < n; k++){  // 終端
          if(d[j][k]> d[j][i] + d[i][k]){No=true;return;}
          if(d[j][k] == d[j][i] + d[i][k]&&!(i==k||i==j)){vis[j][k]=true;}
            d[j][k] = std::min(d[j][k], d[j][i] + d[i][k]);
        }
    }
int main(){
    std::ios_base::sync_with_stdio(false);
    cin>>N;
    REP(i,N)REP(j,N){
        cin>>d[i][j];
    }
    warshall_floyd(N);
    if(No)cout<<"-1";
    else{
        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                //DEB(i)DEB(j)TF(vis[i][j])END
                if(!vis[i][j])ans+=d[i][j];
            }

        }
        cout<<ans;
    }
    return 0;
}

Submission

Task問題 D - Restoring Road Network
User nameユーザ名 Nafmo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 500
Source lengthソースコード長 1835 Byte
File nameファイル名
Exec time実行時間 46 ms
Memory usageメモリ使用量 1024 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_0.txt,subtask0_1.txt,subtask0_2.txt,subtask0_3.txt
All 500 / 500 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01.txt AC 44 ms 1024 KB
02.txt AC 45 ms 1024 KB
03.txt AC 46 ms 1024 KB
04.txt AC 41 ms 1024 KB
05.txt AC 42 ms 1024 KB
06.txt AC 40 ms 1024 KB
07.txt AC 9 ms 1024 KB
08.txt AC 41 ms 1024 KB
09.txt AC 42 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