题意：给你n个点,m条边的图（有向图，记住一定是有向图），给定起点和终点，问你从起点到终点有几条不同的最短路
分析：不同的最短路，即一条边也不能相同，然后刚开始我的想法是找到一条删一条，然后光荣TLE
搜了一下，然后看到网络流，秒懂，就是把所有在最短路上的边重新建一张图，起点到终点的最大流就是解
怎么找到最短路径上的边呢？
在进行dij的时候，每次松弛操作，会更新一个点到起点的最短距离，然后记录一下，对于每一个点
记录有多少点可以走到他可以得到的最短距离，就是记录所有可能的前驱（这里前驱的话，记录边比较好，点比较麻烦）
然后dinic网络流就行
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=1e3+;
const int INF=0x3f3f3f3f;
struct E
{
int u,to,w,next;
bool operator<(const E &rhs)const
{
return w>rhs.w;
}
} edge[*N];
int head[N],tot,n,m,dis[N];
void add(int u,int v,int w)
{
edge[tot].u=u;
edge[tot].to=v;
edge[tot].w=w;
edge[tot].next=head[u];
head[u]=tot++;
}
priority_queue<E>Q;
vector<int>g[N];
bool v[N];
bool dij(int s,int t)
{
for(int i=; i<=n; ++i)dis[i]=INF,v[i]=;
dis[s]=,Q.push(E {,s,,});
while(!Q.empty())
{
while(!Q.empty()&&v[Q.top().to])Q.pop();
if(Q.empty())break;
int u=Q.top().to;
Q.pop();
v[u]=;
for(int i=head[u]; ~i; i=edge[i].next)
{
int to=edge[i].to;
if(dis[to]==dis[u]+edge[i].w)
g[to].push_back(i);
else if(!v[to]&&dis[to]>dis[u]+edge[i].w)
{
g[to].clear(),g[to].push_back(i);
dis[to]=dis[u]+edge[i].w;
Q.push(E {,to,dis[to],});
}
}
}
return dis[t]==INF?false:true;
}
struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int c,int d):from(u),to(v),cap(c),flow(d) {}
};
struct dinic
{
int s,t;
vector<Edge>edges;
vector<int>G[N];
int d[N];
int cur[N];
bool vis[N];
void init()
{
edges.clear();
for(int i=; i<N; ++i)
G[i].clear();
}
bool bfs()
{
memset(vis,,sizeof(vis));
queue<int>q;
q.push(s);
d[s]=;
vis[s]=;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=; i<G[x].size(); i++)
{
Edge &e= edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=;
d[e.to]=d[x]+;
q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int a)
{
if(x==t||a==)return a;
int flow=,f;
for(int &i=cur[x]; i<G[x].size(); i++)
{
Edge &e=edges[G[x][i]];
if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow))))
{
e.flow+=f;
edges[G[x][i]^].flow-=f;
flow+=f;
a-=f;
if(a==)break;
}
}
return flow;
}
int maxflow(int s,int t)
{
this->s=s;
this->t=t;
int flow=;
while(bfs())
{
memset(cur,,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}
void addedge(int u,int v,int c)
{
Edge x(u,v,c,),y(v,u,,);
edges.push_back(x);
edges.push_back(y);
int l=edges.size();
G[u].push_back(l-);
G[v].push_back(l-);
}
} solve;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
for(int i=; i<=n; ++i)g[i].clear();
tot=;
for(int i=; i<=m; ++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(u==v)continue;
add(u,v,w);
}
int s,t;
scanf("%d%d",&s,&t);
if(!dij(s,t))
{
printf("0\n");
continue;
}
solve.init();
for(int i=; i<=n; ++i)
{
for(int j=; j<g[i].size(); ++j)
{
int k=g[i][j];
int u=edge[k].u,v=edge[k].to;
solve.addedge(u,v,);
}
}
printf("%d\n",solve.maxflow(s,t));
}
return ;
}