Submission #1981929
Source Code Expand
// finish date: 2018/01/15
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <map>
#include <climits>
using namespace std;
#define FOR(i, a, b) for(int i=a;i<b;i++)
#define rep(i, n) FOR(i,0,n)
#define ll long long
#define bigmod 1000000007
#define INF 500000000
vector<vector<int>> b, c, field;
int mul(int a, int b) {
return (int) (((ll) (a % bigmod) * (b % bigmod)) % bigmod);
}
int factorial(int n) {
int ans = 1;
FOR(i, 1, n + 1) {
ans = ans * i;
}
return ans;
}
int main() {
int N, M;
cin >> N >> M;
vector<vector<int>> d(N, vector<int>(N, INF));
vector<int> a(M), b(M), c(M);
rep(i, M) {
cin >> a[i] >> b[i] >> c[i];
a[i]--;
b[i]--;
d[a[i]][b[i]] = c[i];
d[b[i]][a[i]] = c[i];
}
rep(i, N) d[i][i] = 0;
rep(k, N) {
rep(i, N) {
rep(j, N) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
vector<int> isMinD(M, false);
rep(i, N) {
rep(j, M) {
if (d[i][a[j]] + c[j] == d[i][b[j]]) {
isMinD[j] = true;
}
}
}
int count = 0;
rep(i, M) if (!isMinD[i]) count++;
cout << count << endl;
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 |
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 |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
1 ms |
256 KB |
subtask_1_03.txt |
AC |
2 ms |
256 KB |
subtask_1_04.txt |
AC |
3 ms |
256 KB |
subtask_1_05.txt |
AC |
3 ms |
256 KB |
subtask_1_06.txt |
AC |
1 ms |
256 KB |
subtask_1_07.txt |
AC |
2 ms |
256 KB |
subtask_1_08.txt |
AC |
3 ms |
256 KB |
subtask_1_09.txt |
AC |
3 ms |
256 KB |
subtask_1_10.txt |
AC |
3 ms |
256 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_12.txt |
AC |
2 ms |
256 KB |
subtask_1_13.txt |
AC |
3 ms |
256 KB |
subtask_1_14.txt |
AC |
3 ms |
256 KB |
subtask_1_15.txt |
AC |
3 ms |
256 KB |
subtask_1_16.txt |
AC |
1 ms |
256 KB |
subtask_1_17.txt |
AC |
1 ms |
256 KB |
subtask_1_18.txt |
AC |
2 ms |
256 KB |
subtask_1_19.txt |
AC |
2 ms |
256 KB |
subtask_1_20.txt |
AC |
1 ms |
256 KB |
subtask_1_21.txt |
AC |
1 ms |
256 KB |
subtask_1_22.txt |
AC |
2 ms |
256 KB |
subtask_1_23.txt |
AC |
2 ms |
256 KB |
subtask_1_24.txt |
AC |
3 ms |
256 KB |
subtask_1_25.txt |
AC |
2 ms |
256 KB |
subtask_1_26.txt |
AC |
2 ms |
256 KB |
subtask_1_27.txt |
AC |
3 ms |
256 KB |
subtask_1_28.txt |
AC |
3 ms |
256 KB |