C++(g++ 7.5.0) 解法, 执行用时: 423ms, 内存消耗: 660K, 提交时间: 2023-06-28 11:43:52

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod =1e9+7;
ll v[10010], w[10010];
int first[10010]; int nex[10010];
int idx;
ll dp1[3000];
ll dp2[3000];
ll dis[3000];
ll ans[5500];
int n, m;
void add(int x, int y, int s) {
        v[++idx] = y; w[idx] = s;
	nex[idx] = first[x];
	first[x] = idx;
}
struct node {
	int x; ll d;
	bool operator<(struct node a)const {
		return d > a.d;
	}
};
int vis[3000];
void init() {
	memset(dp1, 0, sizeof dp1);
	memset(dp2, 0, sizeof(dp2));
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
}
int dj(int x) {
	priority_queue<node>q;
	q.push({ x,0 });
	dis[x] = 0;
	dp1[x] =1;
	while (q.size()) {
		auto it = q.top(); q.pop();
        if(vis[it.x])continue;
        vis[it.x]=1;
		for (int i = first[it.x]; i; i = nex[i]) {
			int j = v[i];
			if (dis[j] > dis[it.x] +w[i]) {
				dis[j] = dis[it.x] +w[i];
				q.push({ j,dis[j] });
				dp1[j] = dp1[it.x];
			}
			else if (dis[j] == dis[it.x] + w[i]) {
				dp1[j] += dp1[it.x];
			}
		}
	}
	return 0;
}
void dfs(int u) {
	if (dp2[u])return ;
	dp2[u] = 1;
	for (int i = first[u]; i; i = nex[i]) {
		int j = v[i];
		   if (dis[j] == dis[u] + w[i]) {
			     dfs(j);
				 dp2[u] += dp2[j];
				 ans[i]=(ans[i]+1ll*dp1[u]*dp2[j]%mod)%mod;
		  }
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, s;
		cin >> x >> y >> s;
		add(x, y, s);
	}
	for (int i = 1; i <= n; i++) {
		init();
		dj(i);
		dfs(i);
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << "\n";
	}

	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 468ms, 内存消耗: 536K, 提交时间: 2022-09-27 20:49:44

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define lowbit(x) x&-x
const int N=1510,M=5010,mod=1e9+7;
#define endl '\n'
int n,m,u,v,c;
int h[N],e[M],ne[M],w[M],idx;
int dp1[N],dp2[N];
int dist[N];
bool vis[N];
ll ans[M];
void add(int a,int b,int c){
	e[++idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx;
}
void init(){
	memset(dp1,0,sizeof dp1);
	memset(dp2,0,sizeof dp2);
	memset(dist,0x3f,sizeof dist);
	memset(vis,0,sizeof vis);
}

void dijkstra(int s){
	priority_queue<pii,vector<pii>,greater<pii>> q;
	dp1[s]=1;
	dist[s]=0;
	q.push({0,s});
	while(!q.empty()){
		auto t=q.top();
		q.pop();
		int u=t.second,d=t.first;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=h[u];i;i=ne[i]){
			int j=e[i];
			if(dist[j]>dist[u]+w[i]){
				dist[j]=dist[u]+w[i];
				q.push({dist[j],j});
				dp1[j]=dp1[u];
			}else if(dist[j]==dist[u]+w[i]){
				dp1[j]+=dp1[u];
			}
		}
	}
}

void dfs(int u,int fa=-1){
	if(dp2[u]) return;
	dp2[u]=1;
	for(int i=h[u];i;i=ne[i]){
		int j=e[i];
		if(dist[j]==dist[u]+w[i]){
			dfs(j);
			dp2[u]+=dp2[j];
			ans[i]=(ans[i]+1ll*dp1[u]*dp2[j]%mod)%mod;
		}
	}

}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>c;
		add(u,v,c);
	}
	for(int i=1;i<=n;i++){
		init();
		dijkstra(i);
		dfs(i);
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
}
int main() {
	int _=1;
	//cin>>_;
	while(_--){
		solve();
	}
	return 0;
}