hdu 3599

         题目意思很简单，对给定图，求其最短路径的条数，且任意两条最短路径没有相同的边。

         这里的做法是：最短路+最大流。首先用dijk算法求出起点到终点的最短路径。然后构造网络流模型。对于图中的任意一条边edge[i]，其两个端点a，b，若存在dis[a]+edge[i].w==dis[b]，则这条边即为最短路上的一条边，可以加入到新图中，并且边的容量为1，流量为0，这是因为每条边只能有一支船队通过。最后用最大流算法的模板一套即可，但此题似乎很卡常数，我的dinic模板tle，换成了EK才过。。。。

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
using namespace std;
const int M=150000;
const int N=1510;
const int inf=1<<29;
struct Node
{
    int u,v;
    int w;
    int next;
}edge[N*N];
int head[N],num;
int n;
int dis[N],que[N*N];
int cap[N][N],pre[N];
vector<int> con[N];

void init()
{
    for(int i=1;i<=n+1;i++)
    {
        head[i]=-1;
    }
    num=0;
}

void addege(int u,int v,int w)
{
    edge[num].u=u;
    edge[num].v=v;
    edge[num].w=w;
    edge[num].next=head[u];
    head[u]=num++;
}

struct cmp
{
    bool operator() (const int &a,const int &b)
    {
        return dis[a]>dis[b];
    }
};

priority_queue<int,vector<int>,cmp > Q;
void dijk()
{
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    dis[1]=0;
    Q.push(1);
    while(!Q.empty())
    {
        int u=Q.top();
        Q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].w)
            {
                dis[v]=dis[u]+edge[i].w;
                Q.push(v);
            }
        }
    }
}


void build()
{
    int front=0,rear=0;
    que[rear++]=1;
    while(front<rear)
    {
        int u=que[front++];
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(dis[u]+edge[i].w==dis[v])
            {
                cap[u][v]=1;
                con[u].push_back(v);
                que[rear++]=v;
            }
        }
    }
}

bool bfs(int n)
{
    int front=0,rear=1,i;
    memset(pre,-1,sizeof(pre));
    pre[1]=0;
    que[0]=1;
    while(front<rear)
    {
        int u=que[front++];
        for(i=0;i<con[u].size();i++)
        {
            int v=con[u][i];
            if(pre[v]==-1&&cap[u][v]>0)
            {
                pre[v]=u;
                if(v==n)return 1;
                que[rear++]=v;
            }
        }
    }
    return 0;
}
int max_flow(int n)
{
    int ans=0;
    while(bfs(n))
    {
        int u=n;
        ans++;
        while(u!=1)
        {
            cap[pre[u]][u]--;
            cap[u][pre[u]]++;
            u=pre[u];
        }
    }
    return ans;
}


int main() 
{
  // freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        init();
        int a,b,c;
        while(1)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(!a && !b && !c) break;
            addege(a,b,c);
            addege(b,a,c);
        }
        dijk();
        if(dis[n]==inf)
        {
            printf("0\n");continue;
        }
        memset(cap,0,sizeof(cap));
        build();
        printf("%d\n",max_flow(n));
    }
    return 0;
}