求源点到终点的不共享边的最短路有多少条.

先求一次单源最短路，得到距离数组d，考虑某条边，它的起点是k1，终点是k2，边的权是c，如果d[k2]-d[k1]=c就说明这条边是最短路上的---wr大牛

原来我的想法是求一次单源最短路得到最短路长度,然后再一次求一次单源最短路并回溯来构造流网络,实在是太菜了而且流网络方面也没有想清楚......

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define maxn 1050
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
struct Edge{int w,wt,next;}e[1000000];
int start[maxn];
int d[maxn];//单源距离

void spfa(int s)
{
    int i,v,N=0;
    deque<int> dq;
    for(v=0;v<n;v++)
        d[v]=inf;
    d[s]=0;
    dq.push_back(s);dq.push_back(n);
    while(!dq.empty())
    {
        v=dq.front();dq.pop_front();
        if(v==n)
        {if(N++>n) return;dq.push_back(n);}
        else
            for(i=start[v];i!=-1;i=e[i].next)
            {
                if(d[e[i].w]>d[v]+e[i].wt)
                {
                    d[e[i].w]=d[v]+e[i].wt;
                    dq.push_back(e[i].w);
                }
            }
    }
}

int flow[maxn][maxn],maxflow[maxn],father[maxn];
int Maxflow,visit[maxn];

void ford_fulkerson(int s,int t)
{
    queue<int>Q;
    int i,u,v;
    while(1)
    {
        //memset(maxflow,0,sizeof(maxflow));//每次寻找增广路径都将每个点的流入容量置为0
        //memset(visit,0,sizeof(visit));//标记一个点是否已经压入队列
        for(i=0;i<n;i++) maxflow[i]=visit[i]=0;
        maxflow[s]=inf;//源点的容量置为正无穷
        Q.push(s);// 将源点压入队列
        while(!Q.empty())
        {
            u=Q.front();
            Q.pop();
            for(v=0;v<n;v++) if(!visit[v]&&flow[u][v]>0)
            {
                visit[v]=1;
                father[v]=u;//记录下他的父亲方便往后的正反向更新
                Q.push(v);
                maxflow[v]=(maxflow[u]<flow[u][v]?maxflow[u]:flow[u][v]);//当前点的容量为父亲点容量与边流量的较小者
            }
            if(maxflow[t]>0)//如果找到了汇点并且汇点容量不为0则清空队列
            {
                while(!Q.empty())
                    Q.pop();
                break;
            }
        }
        if(maxflow[t]==0)//已经找不到到汇点的增广路经了，就退出整个循环
            break;
        for(i=t;i!=s;i=father[i])
        {
            flow[father[i]][i]-=maxflow[t];//正向更新
            flow[i][father[i]]+=maxflow[t];//反向更新
        }
        Maxflow+=maxflow[t];//更新最大流
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif

    int i,v,w,wt,s,t,cnt;
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        cnt=0; for(v=0;v<n;v++) start[v]=-1;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&v,&w,&wt);
            v--;w--;
            e[cnt].w=w;e[cnt].wt=wt;
            e[cnt].next=start[v];start[v]=cnt++;
        }
        scanf("%d%d",&s,&t);
        s--;t--;
        spfa(s);

        //for(v=0;v<n;v++)
                //cout<<v<<":"<<d[v]<<" ";
        //cout<<endl;

        Maxflow=0;
        for(v=0;v<n;v++) for(w=0;w<n;w++) flow[v][w]=0;
        for(v=0;v<n;v++)
            for(i=start[v];i!=-1;i=e[i].next)
            {
                w=e[i].w;
                if(d[w]-d[v]==e[i].wt)
                    flow[v][w]+=1;
            }
        ford_fulkerson(s,t);
        printf("%d\n",Maxflow);
    }
}