题意：N个点M条边的有向图，给定起点S和终点T，求每条边都不重复的S-->T的最短路有多少条。
分析：首先第一步需要找出所有可能最短路上的边。怎么高效地求出呢？可以这样：先对起点S，跑出最短路；对于每条边 e（u，v，w)，若d[u]+w == d[v]。那么e就是最短路上的一条边。在前向星存储的图中遍历即可。网上还有题解用的方法是分别从S和T跑两次最短路，再判断d1[u]+d2[v]+w == d1[T]，其实思路是相似的，但是没必要多跑一遍。
用SPFA就会玄学超时，但其他人却没有；之后改用迪杰斯特拉就跑得很快。
之后问题可转化为求解S到T的最大流。将所求得的最短路的边，建新图，每条边的流量都是1。再用SAP求出S到T的最大流，即最终答案。
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
typedef int LL; const int maxn =1e3+;
const int maxm = 1e5+;
const LL INF =0x3f3f3f3f;
struct Edge{
int from,to;
LL val;
};
struct HeapNode{
LL d; //费用或路径
int u;
bool operator < (const HeapNode & rhs) const{return d > rhs.d;}
};
struct Dijstra{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool used[maxn];
LL d[maxn];
int p[maxn]; void init(int n){
this->n = n;
for(int i=;i<=n;++i) G[i].clear();
edges.clear();
memset(used,,sizeof(used));
} void Addedge(int from,int to ,LL dist){
edges.push_back((Edge){from,to,dist});
m = edges.size();
G[from].push_back(m-);
} void dijkstra(int s){
priority_queue<HeapNode> Q;
for(int i=;i<=n;++i) d[i]=INF;
d[s]=;
Q.push((HeapNode){,s});
while(!Q.empty()){
HeapNode x =Q.top();Q.pop();
int u =x.u;
if(used[u])
continue;
used[u]= true;
for(int i=;i<G[u].size();++i){
Edge & e = edges[G[u][i]];
if(d[e.to] > d[u] + e.val){
d[e.to] = d[u] +e.val;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to],e.to});
}
}
}
}
}G; const int MAXN=;//点数的最大值
const int MAXM=;//边数的最大值 struct Node{
int from,to,next;
int cap;
}; struct SAP_MaxFlow{
int n,m; //点数和边数
int tol;
int head[MAXN];
int dep[MAXN];
int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y
Node edge[MAXM]; void init(int N){
this->n = N;
this->tol=;
memset(head,-,sizeof(head));
} void AddEdge(int u,int v,int w){
edge[tol].from=u;edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];head[u]=tol++;
edge[tol].from=v;edge[tol].to=u;edge[tol].cap=;edge[tol].next=head[v];head[v]=tol++;
} void BFS(int start,int end)
{
memset(dep,-,sizeof(dep));
memset(gap,,sizeof(gap));
gap[]=;
int que[MAXN];
int front,rear;
front=rear=;
dep[end]=;
que[rear++]=end;
while(front!=rear){
int u=que[front++];
if(front==MAXN)front=;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(dep[v]!=-)continue;
que[rear++]=v;
if(rear==MAXN)rear=;
dep[v]=dep[u]+;
++gap[dep[v]];
}
}
}
int SAP(int start,int end)
{
int res=;
BFS(start,end);
int cur[MAXN];
int S[MAXN];
int top=;
memcpy(cur,head,sizeof(head));
int u=start;
int i;
while(dep[start]<n){
if(u==end){
int temp=INF;
int inser;
for(i=;i<top;i++)
if(temp>edge[S[i]].cap){
temp=edge[S[i]].cap;
inser=i;
}
for(i=;i<top;i++){
edge[S[i]].cap-=temp;
edge[S[i]^].cap+=temp;
}
res+=temp;
top=inser;
u=edge[S[top]].from;
}
if(u!=end&&gap[dep[u]-]==)//出现断层，无增广路
break;
for(i=cur[u];i!=-;i=edge[i].next)
if(edge[i].cap!=&&dep[u]==dep[edge[i].to]+)
break;
if(i!=-){
cur[u]=i;
S[top++]=i;
u=edge[i].to;
}
else{
int min=n;
for(i=head[u];i!=-;i=edge[i].next){
if(edge[i].cap==)continue;
if(min>dep[edge[i].to]){
min=dep[edge[i].to];
cur[u]=i;
}
}
--gap[dep[u]];
dep[u]=min+;
++gap[dep[u]];
if(u!=start)u=edge[S[--top]].from;
}
}
return res;
}
}F; //#define LOCAL
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int N,M,s,t,u,v,T;
LL tmp,b;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M);
G.init(N);F.init(N);
for(int i=;i<=M;++i){
scanf("%d%d%d",&u,&v,&tmp);
G.Addedge(u,v,tmp);
}
scanf("%d%d",&s,&t);
G.dijkstra(s);
for(int i=;i<M;++i){
Edge e = G.edges[i];
if(G.d[e.from]+e.val==G.d[e.to])
F.AddEdge(e.from,e.to,);
}
printf("%d\n",F.SAP(s,t));
}
return ;
}