Submission #1070753


Source Code Expand

/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int n, m;
int a[1000], b[1000], c[1000];
int g[100][100];

int main(){
  cin >> n >> m;
  rep(i, n) rep(j, n) g[i][j] = inf;
  rep(i, n) g[i][i] = 0;
  rep(i, m){
    cin >> a[i] >> b[i] >> c[i], a[i]--, b[i]--;
    g[a[i]][b[i]] = g[b[i]][a[i]] = c[i];
  }
  rep(k, n) rep(i, n) rep(j, n) chmin(g[i][j], g[i][k] + g[j][k]);
  int res = 0;
  rep(i, m) res += g[a[i]][b[i]] < c[i];
  cout << res << endl;
}

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User jin_matakich
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1769 Byte
Status AC
Exec Time 4 ms
Memory 256 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 256 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 3 ms 256 KB
subtask_1_27.txt AC 4 ms 256 KB
subtask_1_28.txt AC 4 ms 256 KB