HDU3599 War 求调

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <string.h>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define int              long long

// FOR templates.
#define rep(i, s, n, k)  for(int i = s;i <= n;i += k)
#define repn(i, s, n, k) for(int i = s;i < n;i += k)
#define pre(i, s, n, k)  for(int i = s;i >= n;i -= k)
#define pren(i, s, n, k) for(int i = s;i > n;i -= k)

// Abbr for STL.
#define pii              pair<int, int>
#define pdd              pair<double, double>
#define mpi              map<int, int>
#define vc               vector<int>
#define qi               queue<int>

// IO templates, proven very useful.
#define cn(n)            int n;cin >> n
#define sn(s)            string s;cin >> s
#define pn(p)            pii p;cin >> p.first >> p.second;
#define cm(n)            cin >> n
#define debug            if(isdebug)cout

// Abbr for funcs.
#define pb               push_back
#define mset             memset
#define multitst()       cn(t);while(t--)

// Abbr for simple conditions.

#define pYESNO           _outputstr.setout("YES", "NO")
#define pYesNo           _outputstr.setout("Yes", "No")
#define Yes              _outputstr.out(1)
#define No               _outputstr.out(0)

// #define files

using namespace std;
const int MAXN = 0x3f3f3f3f3f3f3f3fLL;
const int MOD1 = 1000000007LL;
const int MOD2 = 998244353LL;
const int isdebug = 0LL;

int dt[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a % b);
}
inline int lowbit(int x){
	return x & (-x);
}
inline int lcm(int a, int b){
	return a * b / gcd(a, b);
}

class outputstr{
	private:
		string pyes, pno;
	public:
		void set_out(string y, string n){
			pyes = y, pno = n;
		}
		void yn_out(bool yn){
			if(yn) cout << pyes << endl;
			else cout << pno << endl;
		}
};


///// Dinic Algorithm /////

class Flow_Graph{

private:
	struct Flow_Edge{
		int v, cap, id;
	};
	vector<Flow_Edge> gv[20001];
	mpi mp; int n, tot = -1;
	int curr[20001], layer[20001];
	int source, sink;
public:
	void add_edge(int u, int v, int w){
		Flow_Edge k; k.v = v, k.cap = w, k.id = ++tot;
		gv[u].pb(k); mp[tot] = gv[u].size() - 1;
		k.v = u, k.cap = 0LL, k.id = ++tot;
		gv[v].pb(k); mp[tot] = gv[v].size() - 1;
	}
	void init(int k, int sc, int sk){
		n = k, source = sc, sink = sk;
		mp.clear();
		rep(i, 1, 2000, 1)
			gv[i].clear();
		mset(curr, 0LL, sizeof(curr));
		mset(layer, 0LL, sizeof(layer));
		tot = -1;
	}
	bool bfs(){
		rep(i, 1, n, 1) layer[i] = 0LL;
		queue<pii> q;
		q.push(make_pair(source, 1LL));
		layer[source] = 1LL;
		while(!q.empty()){
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for(auto z : gv[x]){
				int to = z.v;
				if(!layer[to] && z.cap > 0){
					layer[to] = y + 1;
					q.push(make_pair(to, y + 1));
				}
			}
		}
		return layer[sink];
	}
	int dfs(int x, int fl){
		if(x == sink) return fl;
		repn(i, curr[x], gv[x].size(), 1){
			curr[x] = i;
			Flow_Edge y = gv[x][i];
			int tmp;
			if(y.cap <= 0 || layer[y.v] != layer[x] + 1)
				continue;
			if((tmp = dfs(y.v, min(fl, y.cap))) > 0){
				gv[x][mp[y.id]].cap -= tmp;
				gv[y.v][mp[y.id ^ 1]].cap += tmp;
				return tmp;
			}
		}
		return 0;
	}
	int Dinic(){
		int ans = 0, fl;
		while(bfs()){
			rep(i, 1, n, 1) curr[i] = 0LL;
			while(fl = dfs(source, MAXN))
				ans += fl;
		}
		return ans;
	}
};

class Graph{
public:
	int dis[20001], vis[20001], n;
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	vector<pii> gv[20001];
	void init(int k){
		n = k;
		while(pq.size()) pq.pop();
		rep(i, 1, n, 1) gv[i].clear();
		mset(dis, MAXN, sizeof(dis));
		mset(vis, 0LL, sizeof(vis));
	}
	void add_edge(int u, int v, int w){
		gv[u].pb(make_pair(v, w));
		gv[v].pb(make_pair(u, w));
	}
	void dijkstra(int k){
		pq.push(make_pair(0LL, k));
		dis[k] = 0LL;
		while(!pq.empty()){
			int x = pq.top().second;
			pq.pop();
			if(vis[x]) continue;
			vis[x] = 1;
			for(auto i : gv[x]){
				int y = i.first, z = i.second; 
				if(dis[x] + z < dis[y]){
					dis[y] = dis[x] + z;
					pq.push(make_pair(z, y));
				}
			}
		}
	}
	
};

void solve(int testcase, ...){
	cn(n); int u, v, w;
	Graph G; Flow_Graph FG;
	G.init(n); FG.init(n, 1, n);
	while(cin >> u >> v >> w && (u || v || w)){
		G.add_edge(u, v, w);
	}
	G.dijkstra(1);
	rep(i, 1, n, 1){
		for(auto x : G.gv[i]){
			if(G.dis[x.first] == G.dis[i] + x.second){
				FG.add_edge(i, x.first, 1LL);
			}
		}
	}
	cout << FG.Dinic() << endl;
}

signed main(){
#ifdef files
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	multitst(){
		solve(t, "War", "Dinic");
	}
#ifdef files
	fclose(stdin); fclose(stdout);
#endif
	return 0;
}