这题需要开O2才能过,本人比较菜,卡了好久....
C++ 代码
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N=5050,P=1e9+7;
int n,m;
int h[N], e[N], ne[N],w[N], idx;
int dist[N],cnt1[N],cnt2[N],ans[N];
bool st[N];
void add(int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra(int x)
{
memset(dist, 0x3f, sizeof dist);
memset(st,0,sizeof st);
memset(cnt1,0,sizeof cnt1);
dist[x] = 0; cnt1[x]=1;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, x}); // first存储距离,second存储节点编号
int tp[N],k=0;
while (heap.size())
{
auto t = heap.top();
heap.pop();
int u = t.second, distance = t.first;
if (st[u]) continue;
st[u] = true;
tp[k++]=u;//存入数组
for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
if (dist[v] > dist[u] + w[i]) //不同就覆盖
{
dist[v] = dist[u] + w[i];
cnt1[v]=cnt1[u];
heap.push({dist[v], v});
}
else if(dist[v]==dist[u]+w[i]){//相同就加上
cnt1[v]+=cnt1[u];
}
}
}
// 反着跑出 cnt2
for(int i=k-1;i>=0;i--){
int u=tp[i];
cnt2[u]=1;
for(int i=h[u];i!=-1;i=ne[i]){
int v=e[i],tw=w[i],id=i+1;//因为idx从0开始所以要加1
if(dist[u]+tw==dist[v]){
cnt2[u]=(cnt2[u]+cnt2[v])%P;
ans[id]=(ans[id]+1ll*cnt1[u]*cnt2[v]%P)%P;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
idx = 0;
memset(h, -1, sizeof h);
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
}
for(int i=1;i<=n;i++) dijkstra(i);
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
}