学步园

大意：求起点到终点的最短距离条数，要求边不重复，点可以重复。

思路：做一次SPFA，然后从原图出发去找边，满足最短路三角不等式的就连一条有向边，容量为1。各种伤不起啊，尼玛，首先是找BUG花掉我2个小时，然后之后无下限TLE，SPFA+Dinic超时，Dijkstra+Dinic超时，Dijkstra+Sap超时，森马情况啊啊啊。后来去看DISCUSS,尼玛，还有0这一顶点的啊。既然，思路知道了，我就不写啦。靠靠靠。。。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

const int MAXN = 10010;
const int MAXM = 50010;
const int INF = 0x3f3f3f3f;

int n, m;
int cnt, cnt2;
int s, t;

int first[MAXN], first2[MAXN];
int level[MAXN];
int d[MAXN];
int q[MAXN];

struct Edge
{
	int v, w, f;
	int next;
}edge[MAXM], edge2[MAXM];

void init()
{
	cnt = cnt2 = 0;
	memset(first, -1, sizeof(first));
	memset(first2, -1, sizeof(first2));
}

void read_graph(int u, int v, int f)
{
	edge[cnt].v = v, edge[cnt].f = f;
	edge[cnt].next = first[u], first[u] = cnt++;
	edge[cnt].v = u, edge[cnt].f = 0;
	edge[cnt].next = first[v], first[v] = cnt++;
}

void read_graph2(int u, int v, int w)
{
	edge2[cnt2].v = v, edge2[cnt2].w = w;
	edge2[cnt2].next = first2[u], first2[u] = cnt2++;
}

void spfa(int src)  
{  
    queue<int> Q;  
    bool inq[MAXN] = {0};  
    for(int i = 1; i <= n; i++) d[i] = (i == src)? 0:INF;  
    Q.push(src);  
    while(!Q.empty())  
    {  
        int x = Q.front(); Q.pop();  
        inq[x] = 0;  
        for(int e = first2[x]; e != -1; e = edge2[e].next)  
        {  
            int v = edge2[e].v, w = edge2[e].w;  
            if(d[v] > d[x] + w)  
            {  
                d[v] = d[x] + w;  
                if(!inq[v])  
                {  
                    inq[v] = 1;  
                    Q.push(v);  
                }  
            }  
        }  
    }  
} 

int bfs(int s, int t)
{
	memset(level, 0, sizeof(level));
	level[s] = 1;
	int front = 0, rear = 1;
	q[front] = s;
	while(front < rear)
	{
		int x = q[front++];
		if(x == t) return 1;
		for(int e  = first[x]; e != -1; e = edge[e].next)
		{
			int v = edge[e].v, f = edge[e].f;
			if(!level[v] && f)
			{
				level[v] = level[x] + 1;
				q[rear++] = v;
			}
		}
	}
	return 0;
}

int dfs(int u, int maxf, int t)
{
	if(u == t) return maxf;
	int ret = 0;
	for(int e = first[u]; e != -1; e = edge[e].next)
	{
		int v = edge[e].v, f = edge[e].f;
		if(level[v] == level[u] + 1 && f)
		{
			int Min = min(maxf-ret, f);
			f = dfs(v, Min, t);
			edge[e].f -= f;
			edge[e^1].f += f;
			ret += f;
			if(ret == maxf) return ret;
		}
	}
	return ret;
}

int Dinic(int s, int t)
{
	int ans = 0;
	while(bfs(s, t)) ans += dfs(s, INF, t);
	return ans;
}

inline void read_case()
{
	init();
	int u, v, w;
	while(scanf("%d%d%d", &u, &v, &w) && (u || v || w))
	{
		read_graph2(u, v, w);
		read_graph2(v, u, w);
	}
}

void build()
{
	spfa(1);
	for(int u = 1; u <= n; u++)
	{
		for(int e = first2[u]; e != -1; e = edge2[e].next)
		{
			int v = edge2[e].v, w = edge2[e].w;
			if(d[v] == d[u] + w)
			{
				read_graph(u, v, 1);
			}
		}
	}
}

void solve()
{
	scanf("%d", &n);
	s = 1, t = n;
	read_case();
	build();
	int ans = Dinic(s, t);
	if(d[t] == INF) { printf("0\n"); return; }
	printf("%d\n", ans);
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		solve();
	}
	return 0;
}