Submission #1057910
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
#define INF 1e9
int n, m;
vector<vector<int> > d; // 隣接行列 適宜0とかINFとか
void warshall_floyd() {
rep (k, n) {
rep (i, n) {
rep (j, n) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
d.assign(n, vi(n, INF));
rep (i, n) {
d[i][i] = 0;
}
vvi all_edge(m);
rep (i, m) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a -= 1; b -= 1;
d[a][b] = d[b][a] = c;
all_edge[i] = {c, min(a, b), max(a, b)};
}
warshall_floyd();
int ans = 0;
rep (i, m) {
if (all_edge[i][0] > d[all_edge[i][1]][all_edge[i][2]]) {
ans += 1;
}
}
printf("%d\n", ans);
return 0;
}
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 |
3 ms |
256 KB |
subtask_1_04.txt |
AC |
4 ms |
256 KB |
subtask_1_05.txt |
AC |
4 ms |
384 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 |
384 KB |
subtask_1_25.txt |
AC |
3 ms |
384 KB |
subtask_1_26.txt |
AC |
3 ms |
256 KB |
subtask_1_27.txt |
AC |
4 ms |
384 KB |
subtask_1_28.txt |
AC |
4 ms |
384 KB |