题目大意：有个人要从A城市去B城市，每条路只允许走一次，问能走几次最短路

解题思路：这题的话，难点就是怎么知道是不是最短路了
首先，先求出到B最短路，这也顺便求出了所有点到B的最短距离
接着求出到A的最短路
这样就能得到两个数组了,假设d1[u]代表u节点到A城市的最短路d2[v]代表v节点到城市B的最短距离
如果满足d1[u] + dis[u][v] + d2[v] == d1[v]的话，那么u，v这条路就属于最短路中的一条边了，那样就可以构边了
得将城市拆成两个点，容量为1

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define N 1010 #define INF 0x3f3f3f3f struct Edge { int from, to, cap, flow; Edge() {} Edge(int from, int to, int cap, int flow): from(from), to(to), cap(cap), flow(flow) {} }; struct ISAP { int p[N], num[N], cur[N], d[N]; int t, s, n, m; bool vis[N]; vector
        
          G[N]; vector
         
           edges; void init(int n) { this->n = n; for (int i = 0; i <= n; i++) { G[i].clear(); d[i] = INF; } edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue
          
            Q; d[t] = 0; vis[t] = 1; Q.push(t); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i] ^ 1]; if (!vis[e.from] && e.cap > e.flow) { vis[e.from] = true; d[e.from] = d[u] + 1; Q.push(e.from); } } } return vis[s]; } int Augment() { int u = t, flow = INF; while (u != s) { Edge &e = edges[p[u]]; flow = min(flow, e.cap - e.flow); u = edges[p[u]].from; } u = t; while (u != s) { edges[p[u]].flow += flow; edges[p[u] ^ 1].flow -= flow; u = edges[p[u]].from; } return flow; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; BFS(); if (d[s] >= n) return 0; memset(num, 0, sizeof(num)); memset(cur, 0, sizeof(cur)); for (int i = 0; i < n; i++) if (d[i] < INF) num[d[i]]++; int u = s; while (d[s] < n) { if (u == t) { flow += Augment(); u = s; } bool ok = false; for (int i = cur[u]; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap > e.flow && d[u] == d[e.to] + 1) { ok = true; p[e.to] = G[u][i]; cur[u] = i; u = e.to; break; } } if (!ok) { int Min = n - 1; for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap > e.flow) Min = min(Min, d[e.to]); } if (--num[d[u]] == 0) break; num[d[u] = Min + 1]++; cur[u] = 0; if (u != s) u = edges[p[u]].from; } } return flow; } }; ISAP isap; #define M 100010 int d1[N], d2[N], n, m, s, t, cnt; int head[N], Next[M], dis[M], to[M]; bool vis[N]; void SPFA(int s, int *d) { for (int i = 1; i <= n; i++) { d[i] = INF; vis[i] = 0; } d[s] = 0; queue
           
             q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = head[u]; i != -1; i = Next[i]) { int v = to[i]; if (d[v] > d[u] + dis[i]) { d[v] = d[u] + dis[i]; if (!vis[v]) { vis[v] = true; q.push(v); } } } } } void add_edges(int u, int v, int d) { to[cnt] = v; dis[cnt] = d; Next[cnt] = head[u]; head[u] = cnt++; } struct Node { int x, y, z; }node[M]; void solve() { scanf(%d%d, &n, &m); cnt = 0; memset(head, -1, sizeof(head)); int x, y, z; for (int i = 0; i < m; i++) { scanf(%d%d%d, &x, &y, &z); node[i].x = x; node[i].y = y; node[i].z = z; if (x == y) continue; add_edges(y, x, z); } scanf(%d%d, &s, &t); SPFA(t, d2); cnt = 0; memset(head, -1, sizeof(head)); for (int i = 0; i < m; i++) { if (node[i].x == node[i].y) continue; add_edges(node[i].x, node[i].y, node[i].z); } SPFA(s, d1); isap.init(n); for (int i = 1; i <= n; i++) for (int j = head[i]; j != -1; j = Next[j]) { int v = to[j]; if (d1[i] + dis[j] + d2[v] == d1[t]) { isap.AddEdge(i, v, 1); } } printf(%d , isap.Maxflow(s, t)); } int main() { int test; scanf(%d, &test); while (test--) { solve(); } return 0; } 
           
          
         
        
       
      
     
    
   

?