Submission #1057907


Source Code Expand

Copy
#include<iostream>
#include<vector>

#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)

using namespace std;

struct Edge{
  int a;
  int b;
  int c;
};


int main(){
  int N, M;
  cin >> N >> M;
  vector<Edge> v(M);
  REP (i, 0, M) {
    cin >> v[i].a >> v[i].b >> v[i].c;
    v[i].a--;
    v[i].b--;
  }

  vector<vector<int> > w(N, vector<int>(N, 1 << 28));
  REP (i, 0, N) w[i][i] = 0;
  REP (i, 0, M) {
    w[v[i].a][v[i].b] = v[i].c;
    w[v[i].b][v[i].a] = v[i].c;
  }
  
  
  REP (k, 0, N) {
    REP (i, 0, N) {
      REP (j, 0, N) {
	w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
      }   
    }
  }

  int ans = 0;
  REP (i, 0, M) {
    if (w[v[i].a][v[i].b] != v[i].c) ans++;
  }

  cout << ans << endl;
  
  return 0;
}

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User commy
Language C++14 (GCC 5.4.1)
Score 400
Code Size 783 Byte
Status AC
Exec Time 5 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 28
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All 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 AC 3 ms 256 KB
sample_02.txt AC 3 ms 256 KB
subtask_1_01.txt AC 3 ms 256 KB
subtask_1_02.txt AC 3 ms 256 KB
subtask_1_03.txt AC 4 ms 256 KB
subtask_1_04.txt AC 4 ms 256 KB
subtask_1_05.txt AC 4 ms 256 KB
subtask_1_06.txt AC 3 ms 256 KB
subtask_1_07.txt AC 3 ms 256 KB
subtask_1_08.txt AC 4 ms 256 KB
subtask_1_09.txt AC 4 ms 256 KB
subtask_1_10.txt AC 4 ms 256 KB
subtask_1_11.txt AC 3 ms 256 KB
subtask_1_12.txt AC 3 ms 256 KB
subtask_1_13.txt AC 4 ms 256 KB
subtask_1_14.txt AC 4 ms 256 KB
subtask_1_15.txt AC 4 ms 256 KB
subtask_1_16.txt AC 3 ms 384 KB
subtask_1_17.txt AC 3 ms 256 KB
subtask_1_18.txt AC 3 ms 256 KB
subtask_1_19.txt AC 3 ms 256 KB
subtask_1_20.txt AC 3 ms 256 KB
subtask_1_21.txt AC 3 ms 256 KB
subtask_1_22.txt AC 3 ms 256 KB
subtask_1_23.txt AC 3 ms 256 KB
subtask_1_24.txt AC 4 ms 256 KB
subtask_1_25.txt AC 3 ms 256 KB
subtask_1_26.txt AC 4 ms 256 KB
subtask_1_27.txt AC 5 ms 256 KB
subtask_1_28.txt AC 5 ms 256 KB