Submission #1070211
Source Code Expand
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<climits> //INT_MIN/MAX
using namespace std;
#define FOR(i,s,e) for(ll (i)=(s);(i)<(e);(i)++)
#define FORR(i,s,e) for(ll (i)=(s);(i)>(e);(i)--)
#define MOD 1000000007
#define debug(x) cout<<#x<<": "<<x<<endl
typedef long long ll;
/* 2017/01/18 問題 ----- abc051 d /Link http://abc051.contest.atcoder.jp/tasks/abc051_d */
/* -----解説等-----
問題:
*/
#define INF 10000000
int d[110][110];
int s[1010];
int t[1010];
int c[1010];
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int M; int N;
cin >> N >> M;
FOR(i, 0, N) { //for Warshall
FOR(j, 0, N) {
if (i == j)d[i][j] = 0;
else d[i][j] = INF;
}
}
FOR(i, 0, M) {
cin >> s[i] >> t[i] >> c[i];
s[i]--; t[i]--;
d[s[i]][t[i]] = c[i];
d[t[i]][s[i]] = c[i];
}
FOR(k, 0, N) {
FOR(i, 0, N) {
if (d[i][k] < INF)
FOR(j, 0, N) {
if (d[k][j] == INF)continue;
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
//使用したかのチェック
ll ans=0;
FOR(i, 0, M) {// M辺についてcheck
int yes = 1;
FOR(j, 0, N) {
FOR(k, 0, N) {
if(j!=k)
//最短経路であるか否か
if (d[j][k] == d[j][s[i]] + c[i] + d[t[i]][k])yes = 0;
}
}
ans += yes;
}
cout << ans << 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 |
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 |
2 ms |
256 KB |
subtask_1_02.txt |
AC |
3 ms |
256 KB |
subtask_1_03.txt |
AC |
5 ms |
256 KB |
subtask_1_04.txt |
AC |
5 ms |
256 KB |
subtask_1_05.txt |
AC |
14 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 |
5 ms |
256 KB |
subtask_1_09.txt |
AC |
5 ms |
256 KB |
subtask_1_10.txt |
AC |
5 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 |
5 ms |
256 KB |
subtask_1_14.txt |
AC |
6 ms |
256 KB |
subtask_1_15.txt |
AC |
6 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 |
4 ms |
256 KB |
subtask_1_19.txt |
AC |
6 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 |
4 ms |
256 KB |
subtask_1_23.txt |
AC |
4 ms |
256 KB |
subtask_1_24.txt |
AC |
17 ms |
256 KB |
subtask_1_25.txt |
AC |
9 ms |
256 KB |
subtask_1_26.txt |
AC |
9 ms |
256 KB |
subtask_1_27.txt |
AC |
21 ms |
256 KB |
subtask_1_28.txt |
AC |
22 ms |
256 KB |