Submission #1127417

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using int64 = int64_t;

using P = pair<int, int>;

constexpr int64 MOD = 1000000007;
constexpr int INF = MOD;

struct state {
    int pos, dist;
    state () {}
    state (int a, int b): pos(a), dist(b) {}
    bool operator < (const state &o) const { return dist > o.dist; }
};

struct edge {
    int to, dist, id;
    edge() {}
    edge(int b, int c, int id): to(b), dist(c), id(id) {}
};

int N, M;

vector<vector<edge>> graph;

vector<int> used;

// P = pair< `prev`, `edge_id` >
int main() {
    cin >> N >> M;
    graph.resize(N);
    used.resize(M);
    int edge_id = 0;
    for (int j = 0; j < M; ++j) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        graph[a].emplace_back(b, c, edge_id);
        graph[b].emplace_back(a, c, edge_id);
        edge_id++;
    }

    assert(edge_id == M);
    fill(begin(used), end(used), 0);

    vector<P> prev(N);
    for (int j = 0; j < N; ++j) {
        vector<int> dist(N);
        fill(begin(dist), end(dist), INF);
        fill(begin(prev), end(prev), make_pair(-1, -1));

        priority_queue<state> pq;
        pq.emplace(j, 0);
        dist[j] = 0;
        while (!pq.empty()) {
            state st = pq.top(); pq.pop();
            if (st.dist > dist[st.pos]) { continue; }

            for (const edge& e : graph[st.pos]) {
                if (st.dist + e.dist < dist[e.to]) {
                    dist[e.to] = st.dist + e.dist;
                    prev[e.to] = make_pair(st.pos, e.id);
                    pq.emplace(e.to, dist[e.to]);
                }
            }
        }

        for (int k = 0; k < N; ++k) {
            int pos = k;
            while (pos != j) {
                P p = prev[pos];
                used[p.second] = 1;
                pos = p.first;
            }
        }
    }

    int ans = 0;
    for (int j = 0; j < M; ++j) {
        if (!used[j]) {
            ++ans;
        }
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result