Submission #1057090
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 2e9
int n, m;
vector<vector<int> > cost; // 隣接行列
vector<int> d; // 仮のコストの最小値、最終結果
deque<bool> used;
vector<set<pii> > route;
void dijkstra(int s) {
d.assign(n, INF);
used.assign(n, false);
d[s] = 0;
while (true) {
int v = -1;
rep (u, n) {
if (!used[u] && (v == -1 || d[u] < d[v])) {
v = u;
}
}
if (v == -1) {
break;
}
used[v] = true;
rep (u, n) {
if (d[u] > d[v] + cost[v][u]) {
route[u] = route[v];
route[u].insert({min(v, u), max(v, u)});
d[u] = d[v] + cost[v][u];
} else if (d[u] == d[v] + cost[v][u]) {
route[u].insert({min(v, u), max(v, u)});
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
cost.assign(n, vi(n, INF));
rep (i, n) {
cost[i][i] = 0;
}
set<pii> all_edge;
rep (i, m) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a -= 1; b -= 1;
cost[a][b] = cost[b][a] = c;
all_edge.insert(make_pair(min(a, b), max(a, b)));
}
route.resize(n);
rep (i, n) {
rep (j, n) {
route[j].clear();
}
dijkstra(i);
rep (j, n) {
for (pii p : route[j]) {
all_edge.erase(p);
}
}
}
printf("%d\n", (int)all_edge.size());
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 |
7 ms |
384 KB |
subtask_1_03.txt |
AC |
16 ms |
512 KB |
subtask_1_04.txt |
AC |
42 ms |
768 KB |
subtask_1_05.txt |
AC |
19 ms |
384 KB |
subtask_1_06.txt |
AC |
4 ms |
256 KB |
subtask_1_07.txt |
AC |
10 ms |
384 KB |
subtask_1_08.txt |
AC |
22 ms |
512 KB |
subtask_1_09.txt |
AC |
33 ms |
512 KB |
subtask_1_10.txt |
AC |
18 ms |
384 KB |
subtask_1_11.txt |
AC |
3 ms |
256 KB |
subtask_1_12.txt |
AC |
5 ms |
256 KB |
subtask_1_13.txt |
AC |
8 ms |
384 KB |
subtask_1_14.txt |
AC |
12 ms |
384 KB |
subtask_1_15.txt |
AC |
9 ms |
384 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 |
384 KB |
subtask_1_20.txt |
AC |
3 ms |
256 KB |
subtask_1_21.txt |
AC |
3 ms |
256 KB |
subtask_1_22.txt |
AC |
7 ms |
256 KB |
subtask_1_23.txt |
AC |
5 ms |
256 KB |
subtask_1_24.txt |
AC |
16 ms |
384 KB |
subtask_1_25.txt |
AC |
8 ms |
384 KB |
subtask_1_26.txt |
AC |
12 ms |
384 KB |
subtask_1_27.txt |
AC |
22 ms |
384 KB |
subtask_1_28.txt |
AC |
9 ms |
384 KB |