题意

C国有n座城市，城市之间通过m条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。n≤1500、m≤5000、w≤10000

题解

这题其实很简单
然后不知道为什么，耗了我一个中午。。
看来思维确实要康复一下了。。
考虑到n很小，你不妨可以枚举起点，然后暴力跑一次最短路
建一个最短路径图
然后对于一个点，他所可以增加的道路就是
$(起点到x的方案数)*(y可以扩展的方案数)$
CODE:

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const LL MOD=1000000007;
const LL N=5005;
LL n,m;
struct qq
{LL x,y,z;LL last;
}e[N];LL num,last[N];
qq E[N];LL Num,Last[N];//最短路径图 
void init (LL x,LL y,LL z)
{num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
LL d[N];
void Init (LL x,LL y)
{Num++;d[y]++;E[Num].x=x;E[Num].y=y;E[Num].last=Last[x];Last[x]=Num;
}
LL f[N];
bool vis[N];
LL g[2][N];//起点开始有多少个点可以到他 它可以到多少个点 
void Get (LL X)
{queue<int> q;for (LL u=1;u<=n;u++)   if (d[u]==0)q.push(u);while (!q.empty()){LL x=q.front();q.pop();for (LL u=Last[x];u!=-1;u=E[u].last){LL y=E[u].y;g[X][y]=g[X][y]+g[X][x];d[y]--;if (d[y]==0)    q.push(y);}}
}
LL ans[N];
void SPFA (LL x)
{memset(vis,false,sizeof(vis));memset(f,127,sizeof(f));queue<int> q;q.push(x);f[x]=0;vis[x]=true;while (!q.empty()){LL x=q.front();q.pop();for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (f[y]>f[x]+e[u].z){f[y]=f[x]+e[u].z;if (vis[y]==false){vis[y]=true;q.push(y);}}}vis[x]=false;}memset(d,0,sizeof(d));Num=0;memset(Last,-1,sizeof(Last));for (LL u=1;u<=num;u++){LL x=e[u].x,y=e[u].y;if (f[y]==f[x]+e[u].z)Init(x,y);}for (LL u=1;u<=n;u++) g[0][u]=0;g[0][x]=1;Get(0);memset(d,0,sizeof(d));Num=0;memset(Last,-1,sizeof(Last));for (LL u=1;u<=num;u++){LL x=e[u].x,y=e[u].y;if (f[y]==f[x]+e[u].z)Init(y,x);}for (LL u=1;u<=n;u++) g[1][u]=1;Get(1);for (LL u=1;u<=num;u++){LL x=e[u].x,y=e[u].y;if (f[y]==f[x]+e[u].z)//如果是的话ans[u]=(ans[u]+g[0][x]*g[1][y]%MOD)%MOD;}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%lld%lld",&n,&m);for (LL u=1;u<=m;u++){LL x,y,z;scanf("%lld%lld%lld",&x,&y,&z);init(x,y,z);}for (LL u=1;u<=n;u++)//枚举一个起点SPFA(u); for (LL u=1;u<=m;u++)   printf("%lld\n",ans[u]);return 0;
}