Q - Marriage Match IV

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

3
7 8
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
5 7 1
6 7 1
1 7

6 7
1 2 1
2 3 1
1 3 3
3 4 1
3 5 1
4 6 1
5 6 1
1 6

2 2
1 2 1
1 2 2
1 2
Sample Output
2
1
1

• There are several shortest paths for A person from city A to city B. here we need to pay special attention to: each path can only be taken once, and after that, we can't go any more, and we can only take the shortest path
• Idea: remove the points and edges that are not the shortest path (there may be several shortest paths here), and re create a new graph with the remaining edges. Set the edge weight to 1, and run the maximum flow once.
  So how can we judge whether an edge is the edge of the shortest path?
  Let's make some assumptions first:

1. Suppose the edge to be judged is (u, v), its length is w (u, v), the source point of the graph is s, and the sink point is e.
2. The shortest distance from s to other points of the shortest to forward running is stored in the dis1 [] array,
   Dis [u] is the shortest distance from s to u;
3. The shortest distance from e to other points in the dis2 [] array is the shortest distance from u to e (note that this direction is u to v)

• Finally, we just need to traverse each given edge:
  If dis1 [u] + W (U, V) + dis2 [v] = dis1 [e] is true. Then we can judge that this edge is the edge of the shortest path.
  Finally, we can get the number of path schemes by running the maximum flow of these edge new graphs.
• In fact, we have to consider the rest: why does the biggest stream come out with the answer?????????

Problem solving (SPFA + ISAP)

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

#define INF 0x3f3f3f3f
const int maxn = 10005;
const int maxm = 200005;

struct Edge
{
    int v,w,next;
} edge1[maxm], edge2[maxm], edge[maxm];
int n,m,s,e;
int head1[maxn], head2[maxn], head[maxn];
int dis1[maxn], dis2[maxn];
int use[maxn];

int k1,k2,k;
void Add(int u, int v, int w, int head[], int & k, Edge edge[])
{
    edge[++ k] = (Edge){ v, w, head[u]}; head[u] = k;
}

void Spfa(int s, int dis[], int head[], Edge edge[])
{
    for(int i = 1; i <= n; i ++)
        dis[i] = INF,use[i] = 0;
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    int u,v,w;
    while(! q.empty())
    {
        u = q.front();
        q.pop();
        use[u] = 0;

        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            v = edge[i].v;
            w = edge[i].w;
            if(dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if(! use[v])
                {
                    q.push(v);
                    use[v] = 1;
                }
            }
        }
    }
}

int deep[maxn], num[maxn];
int cur[maxn], last[maxm];

void bfs(int e)
{
    for(int i = 0; i <= n; i ++)
        deep[i] = n, cur[i] = head[i], use[i] = 0;
    deep[e] = 0;
    queue<int> q;
    q.push(e);
    int u, v;
    while(! q.empty())
    {
        u = q.front(); q.pop();
  //      use[u] = 0;

        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            v = edge[i].v;
            if(edge[i^1].w && deep[v] == n)      //The positive graph edge exists and the node v has not been found
            {
                deep[v] = deep[u] + 1;
                    q.push(v);
//                if(! use[v])
//                {
//                    q.push(v);
//                    use[v] = 1;
//                }
            }
        }
    }
}

int Add_flow(int s, int e)
{
    int ans = INF;
    int now = e;
    while(now != s)
    {
        ans = min(ans, edge[last[now]].w);
        now = edge[last[now]^1].v;
    }
    now = e;
    while(now != s)
    {
        edge[last[now]].w -= ans;
        edge[last[now]^1].w += ans;
        now = edge[last[now]^1].v;
    }
    return ans;
}

int isap(int s, int e)
{
    int now = s;    //Start from the starting point
    bfs(e);         //First, find out a polishing path with the edge being operated
    for(int i = 1; i <= n; i ++) num[deep[i]] ++;
    int mx_flw = 0;
    while(deep[s] < n)
    {
        if(now == e)        //If it reaches the convergence point and expands directly, it will return to the source point for the next round of augmentation
        {
            mx_flw += Add_flow(s, e);
            now = s;
        }
        bool has_find = 0;
        for(int i = cur[now]; i != -1; i = edge[i].next)
        {
            if(edge[i].w && deep[now] == deep[edge[i].v] + 1)
            {
                has_find = 1;   //Marking has found a way
                cur[now] = i;     //Optimize current arc
                now = edge[i].v;
                last[edge[i].v] = i;
                break;
            }
        }

        if(! has_find)
        {
            int minn = n - 1;
            for(int i = head[now]; i != -1; i = edge[i].next)
                if(edge[i].w)
                    minn = min(minn, deep[edge[i].v]);
            if( (-- num[deep[now]]) == 0) break;   //gap optimization leads to fault
            num[deep[now] = minn + 1] ++;
            cur[now] = head[now];
            if(now != s)
                now = edge[last[now]^1].v;
        }
    }
    return mx_flw;
}


void init()
{
    k1 = 0; k2 = 0; k = -1;
    for(int i = 0; i <= n; i ++)
        head1[i] = -1, head2[i] = -1, head[i] = -1;

    memset(num, 0, sizeof(num));
}

int main()
{
    //freopen("T.txt","r",stdin);
    int t;
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d %d", &n, &m);
        init();
        int u, v, w;
        for(int i = 1; i <= m; i ++)
        {
            scanf("%d %d %d", &u, &v, &w);
            Add(u, v, w, head1, k1, edge1);
            Add(v, u, w, head2, k2, edge2);
        }
        scanf("%d %d", &s, &e);
        Spfa(s, dis1, head1, edge1);
        Spfa(e, dis2, head2, edge2);

        //Go through all the edges in the graph to find the shortest edge
        for(int i = 1; i <= m; i ++)
        {
            u = edge2[i].v;
            v = edge1[i].v;
            w = edge1[i].w;
            if(dis1[u] + w + dis2[v] == dis1[e])
            {
                Add(u, v, 1, head, k, edge);
                Add(v, u, 0, head, k, edge);
            }
        }
        printf("%d\n", isap(s, e));
    }

    reurn 0;
}