# Marriage Match IV

Problem Description
Do not sincere non-interference。
Like that show, now starvae also take part in a show, but it take place between city A and B. Starvae is in city A and girls are in city B. Every time starvae can get to city B and make a data with a girl he likes. But there are two problems with it, one is starvae must get to B within least time, it's said that he must take a shortest path. Other is no road can be taken more than once. While the city starvae passed away can been taken more than once.

So, under a good RP, starvae may have many chances to get to city B. But he don't know how many chances at most he can make a data with the girl he likes . Could you help starvae?

Input
The first line is an integer T indicating the case number.(1<=T<=65)
For each case,there are two integer n and m in the first line ( 2<=n<=1000, 0<=m<=100000 ) ,n is the number of the city and m is the number of the roads.

Then follows m line ,each line have three integers a,b,c,(1<=a,b<=n,0<c<=1000)it means there is a road from a to b and it's distance is c, while there may have no road from b to a. There may have a road from a to a,but you can ignore it. If there are two roads from a to b, they are different.

At last is a line with two integer A and B(1<=A,B<=N,A!=B), means the number of city A and city B.
There may be some blank line between each case.

Output
Output a line with a integer, means the chances starvae can get at most.

Sample Input
```37 81 2 11 3 12 4 13 4 14 5 14 6 15 7 16 7 11 76 71 2 12 3 11 3 33 4 13 5 14 6 15 6 11 62 21 2 11 2 21 2
```

Sample Output
```211
```

#include <stdio.h>
#include
<string.h>
#include
<queue>
#include
<algorithm>
#include
<iostream>
#define Min(a, b) (a) < (b) ? a : b
#define Max(a, b) (a) > (b) ? a : b
using  namespace std;
const  int MAXN = 2005;
const  int MAXM = 210000;
const  int INF = 1100000000;
struct  Edge
{

int  st, ed;

int  next;

int  flow;

int cap;
}edge[MAXM];
void  add(int u, int v, int w)
{
edge[E].flow
= 0;
edge[E].cap
= w;
edge[E].st
= u;
edge[E].ed
= v;
edge[E].next
= E++;
edge[E].flow
= 0
edge[E].cap
= 0
edge[E].st
= v;
edge[E].ed
= u;
edge[E].next
= E++;
}
int  dinic_bfs(int src, int dest, int ver)
{

int i, j;

for (i = 0; i <= ver; i++)
{
level[i]
= -1;
}

int rear = 1;
que[
0= src; level[src] = 0;

for(i = 0; i < rear; i++
{

for(j = head[que[i]]; j != -1; j = edge[j].next)
{

if(level[edge[j].ed] == -1 && edge[j].cap > edge[j].flow)
{
level[edge[j].ed]
= level[que[i]]+1;
que[rear
++= edge[j].ed;
}
}
}

return  level[dest] >= 0;
}

int dinic_dfs(int src, int dest, int ver)
{

int stk[MAXN], top = 0;

int ret = 0, cur, ptr, pre[MAXN], minf, i;

int del[MAXN];

for (i = 0; i <= ver; i++
{
del[i]
= 0;
}
stk[top
++= src;
pre[src]
= src;
cur
= src;

while(top)
{

while(cur != dest && top)
{

for(i = head[cur]; i != -1; i = edge[i].next)
{

if(level[edge[i].ed] == level[cur] + 1 && edge[i].cap > edge[i].flow  && !del[edge[i].ed])
{
stk[top
++= edge[i].ed;
cur
= edge[i].ed;
pre[edge[i].ed]
= i;

break;
}
}

if(i == -1)
{
del[cur]
= 1;
top
--;

if(top) cur = stk[top-1];
}
}

if(cur == dest)
{
minf
= INF;

while(cur != src)
{
cur
= pre[cur];

if(edge[cur].cap - edge[cur].flow < minf) minf = edge[cur].cap - edge[cur].flow;
cur
= edge[cur].st;
}
cur
= dest;

while(cur != src)
{
cur
= pre[cur];
edge[cur].flow
+= minf;
edge[cur
^1].flow -= minf;

if(edge[cur].cap - edge[cur].flow == 0)
{
ptr
= edge[cur].st;
}
cur
= edge[cur].st;
}

while(top > 0&& stk[top-1!= ptr) top--;

if(top)  cur = stk[top-1];
ret
+= minf;
}
}

return ret;
}
int Dinic(int src, int dest, int ver)
{

int  ret = 0, t;

while(dinic_bfs(src, dest, ver))
{
t
= dinic_dfs(src, dest, ver);

if(t) ret += t;

else  break;
}

return ret;
}
//下面是求最短路用到的数据结构。
struct T
{

int v, w, next;
}fn[MAXM];
int th, g[MAXN], dis1[MAXN], dis2[MAXN], pre[MAXN], visit[MAXN];
int map[MAXN][MAXN], cat[MAXN][MAXN];
void insert(int u, int v, int w)
{
fn[th].v
= v, fn[th].w = w, fn[th].next = g[u], g[u] = th++;
}
void spfa(int s, int t, int n, int * dis, int sign)
{

int i, j, u, v;
th
= 0;

for (i = 0; i <= n; i++)
{
g[i]
= -1;
}

for (i = 1; i <= n; i++)
{

for (j = 1; j <= n; j++)
{

if (map[i][j] < INF)
{

if (sign)
{
insert(i, j, map[i][j]);
}

else
{
insert(j, i, map[i][j]);
}
}
}
}

for (i = 0; i <= n; i++)
{
visit[i]
= 0;
dis[i]
= INF;
}
queue
<int> que;
dis[s]
= 0, visit[s] = 1;
que.push(s);

while (!que.empty())
{
u
= que.front();
que.pop();
visit[u]
= 0;

for (i = g[u]; i != -1; i = fn[i].next)
{
v
= fn[i].v;

if (dis[v] > dis[u] + fn[i].w)
{
dis[v]
= dis[u] + fn[i].w;

if (!visit[v])
{
que.push(v);
visit[v]
= 1;
}
}
}
}
}
void build (int s, int t, int n)
{

int i, j, v;
E
= 0;

for (i = 0; i <= n + 10; i++)
{
= -1;
}

for (i = 1; i <= n; i++)
{

for (j = g[i]; j != -1; j = fn[j].next)
{
v
= fn[j].v;

if (dis1[i] + dis2[v] + fn[j].w == dis1[t])//对所有边满足最短路上的边建图。
{
}
}
}

int ans = Dinic(s, t, n + 10);
printf(
"%d\n", ans);
}
int main()
{

int t, n, m, ver, i, j, u, v, w;
scanf(
"%d"&t);

while (t--)
{
scanf(
"%d%d"&n, &m);

for (i = 1; i <= n; i++)
{

for (j = 1; j <= n; j++)
{
map[i][j]
= INF;
cat[i][j]
= 0;
}
}

while (m--)
{
scanf(
"%d%d%d"&u, &v, &w);

if (u != v)
{

if (map[u][v] > w)
{
map[u][v]
= w;
cat[u][v]
= 1;
}

else if (map[u][v] == w)
{
cat[u][v]
++;//边容量++
}
}
}

int s, t, flow;
scanf(
"%d%d"&s, &t);
spfa(t, s, n, dis2,
0);
spfa(s, t, n, dis1,
1);
build(s, t, n);
}

return 0;
}
/*
2 2
1 2 1
1 2 2
1 2

2 1
1 2 1
1 2

3 2
1 2 1
2 3 4

*/