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
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
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 |