2958번: 도로 네트워크 - 최적화 필요

https://www.acmicpc.net/problem/2958

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N = 1500, MAX_M = 5000, prime = 1000000007;
struct st {
    int x, w, idx;
    bool operator<(st i) const {
        return w > i.w;
    }
};
vector<st> adj[MAX_N + 1];
int n, m, dist[MAX_N + 1], cnt[MAX_N + 1], cnt2[MAX_N + 1], res[MAX_M];
bool ed[MAX_M], ck[MAX_N + 1];
priority_queue<st> pq;
void dfs(int h) {
    if (cnt2[h]) return;
    cnt2[h]++;
    for (auto t : adj[h]) {
        if (!ed[t.idx]) continue;
        dfs(t.x);
        cnt2[h] = (cnt2[h] + cnt2[t.x]) % prime;
        res[t.idx] = (res[t.idx] + (long long)cnt[h] * cnt2[t.x]) % prime;
    }
}
void fpath(int s) {
    fill(dist + 1, dist + 1 + n, 1e9);
    fill(ed, ed + m, false);
    fill(cnt2 + 1, cnt2 + 1 + n, 0);
    fill(ck + 1, ck + 1 + n, false);
    dist[s] = 0; cnt[s] = 1;
    pq.push({ s,0,-1 });
    while (!pq.empty()) {
        int h = pq.top().x, dis = pq.top().w, idx = pq.top().idx;
        pq.pop();
        if (dis != dist[h]) continue;
        ed[idx] = true;
        if (ck[h]) continue;
        ck[h] = true;
        for (auto t : adj[h]) {
            if (dist[t.x] >= dis + t.w) {
                if (dist[t.x]>dis + t.w)cnt[t.x] = 0;
                cnt[t.x] = (cnt[t.x] + cnt[h]) % prime;
                pq.push({ t.x,dist[t.x] = dis + t.w,t.idx });
            }
        }
    }
    dfs(s);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b,c,i });
    }
    for (int i = 1; i <= n; i++) fpath(i);
    for (int i = 0; i < m; i++) printf("%d\n", res[i]);
    return 0;
}