Submission #1243163


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 10000000;
int N, M;
int  G[101][101];
int dist[101][101];
int a[1001],b[1001],c[1001];
int ans;

void d_init () {
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      dist[i][j] = INF;
    }
  }

  for(int i = 0; i < N; i++) {
    dist[i][i] = 0;
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(G[i][j]) dist[i][j] = G[i][j];
    }
  }
}

int main() {
  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;
    G[a[i]][b[i]] = c[i];
    G[b[i]][a[i]] = c[i];
  }

  d_init();
  
  
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      for(int k = 0; k < N; k++) {
	dist[j][k] = min(dist[j][k],dist[j][i] + dist[i][k]);
      }
    }
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cout << dist[i][j] <<endl;
    }
  }

  for(int i = 0; i < M; i++) {
    for(int j = 0; j < N; j++) {
      for(int k = 0; k < N; k++) {
	if(j == k)continue;
	if(dist[j][a[i]] + c[i] + dist[b[i]][k] == dist[j][k]){ ans++;
	  cout <<dist[j][a[i]]<<"  "<< c[i] << "   " << dist[b[i]][k] <<"aaa"<<dist[j][k]<<endl;}
      }
    }
  }
  cout << M - ans/2 <<endl;
}



  

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User shossie1016
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1353 Byte
Status WA
Exec Time 324 ms
Memory 4480 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
WA × 2
WA × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt
Case Name Status Exec Time Memory
sample_01.txt WA 1 ms 256 KB
sample_02.txt WA 1 ms 256 KB
subtask_1_01.txt WA 3 ms 256 KB
subtask_1_02.txt WA 37 ms 640 KB
subtask_1_03.txt WA 104 ms 1408 KB
subtask_1_04.txt WA 324 ms 4480 KB
subtask_1_05.txt WA 66 ms 768 KB
subtask_1_06.txt WA 9 ms 384 KB
subtask_1_07.txt WA 62 ms 1024 KB
subtask_1_08.txt WA 148 ms 2048 KB
subtask_1_09.txt WA 253 ms 3456 KB
subtask_1_10.txt WA 103 ms 1408 KB
subtask_1_11.txt WA 5 ms 256 KB
subtask_1_12.txt WA 17 ms 384 KB
subtask_1_13.txt WA 37 ms 512 KB
subtask_1_14.txt WA 45 ms 640 KB
subtask_1_15.txt WA 38 ms 512 KB
subtask_1_16.txt WA 2 ms 256 KB
subtask_1_17.txt WA 4 ms 256 KB
subtask_1_18.txt WA 8 ms 256 KB
subtask_1_19.txt WA 16 ms 384 KB
subtask_1_20.txt WA 4 ms 256 KB
subtask_1_21.txt WA 3 ms 256 KB
subtask_1_22.txt WA 25 ms 512 KB
subtask_1_23.txt WA 10 ms 384 KB
subtask_1_24.txt WA 59 ms 640 KB
subtask_1_25.txt WA 26 ms 384 KB
subtask_1_26.txt WA 41 ms 512 KB
subtask_1_27.txt WA 82 ms 768 KB
subtask_1_28.txt WA 56 ms 512 KB