题目：有n个城市，m条不相同的有向边，给一个起点st和终点ed，每条路只能走一次，问在保证从起点到终点的路程最短的情况下，有几条路可以走？
感想+题解：显然就是先构建一个新图跑最短路，然后把不符合的边去掉，或者说把可以构成最短路的边加到一个新图里面跑最大流，最短路和最大流就是模板的问题，问题就是怎么构建一个新图跑最大流。我的思路如下：
正向跑一遍最短路得到d[i]，其中d[i]表示起点st到点i的最短路
反向跑一遍最短路得到dd[i]，其中dd[i]表示终点到节点i的最短距离
判断能不能把x–y这条边加进去，显然就是d[x]+dd[y]+w(x,y)=d[1]
就是起点到x的最短距离+x到y的距离+y到终点的最短距离=起点到终点最短距离
然后至于代码有点…长

讯享网

#include<iostream> #include<vector> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #define ll long long #define ull unsigned long long #define ld long double #define rep1(i,n) for(int i=1;i<=n;i++) #define rep0(i,n) for(int i=0;i<n;i++) #define rep(i,l,r) for(int i=l;i<=r;i++) using namespace std; const ll mod=; const int maxn=1000+7,M=3e5+7,INF=0x3f3f3f3f; int n,m,mp[maxn][maxn],st,ed,num[maxn][maxn]; int dd[maxn],d[maxn]; bool v[maxn]; vector<int>e[maxn],ee[maxn]; int head[M],Next[M],edge[M],ver[M],tot,maxflow,incf[M],pre[M]; void add(int x,int y,int z) { 
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot; ver[++tot]=x,edge[tot]=0,Next[tot]=head[y],head[y]=tot; } void dij1()//正图跑最短路 { 
    priority_queue<pair<int,int> >q; memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); d[st]=0;//d[i]表示起点st到点i的最短路 q.push(make_pair(0,st)); while(q.size()) { 
    int x=q.top().second;q.pop(); if(v[x])continue; for(int i=0;i<e[x].size();i++) { 
    int y=e[x][i],z=mp[x][y]; if(d[y]>d[x]+z) { 
    d[y]=d[x]+z; q.push(make_pair(-d[y],y)); } } } } void dij2()//反图跑最短路 { 
    priority_queue<pair<int,int> >q; memset(dd,0x3f,sizeof(dd)); memset(v,0,sizeof(v)); dd[ed]=0;//dd[i]表示终点到节点i的最短距离 q.push(make_pair(0,ed)); while(q.size()) { 
    int x=q.top().second;q.pop(); if(v[x])continue; for(int i=0;i<ee[x].size();i++) { 
    int y=ee[x][i],z=mp[y][x]; if(dd[y]>dd[x]+z) { 
    dd[y]=dd[x]+z; q.push(make_pair(-dd[y],y)); } } } } bool bfs()//增广路算法 { 
    memset(v,0,sizeof(v)); queue<int>q; q.push(st);v[st]=1; incf[st]=INF;//增广路上各边最小剩余容量 while(q.size()) { 
    int x=q.front();q.pop(); for(int i=head[x];i;i=Next[i]) if(edge[i]) { 
    int y=ver[i]; if(v[y])continue; incf[y]=min(incf[x],edge[i]); pre[y]=i; q.push(y),v[y]=1; if(y==ed)return 1; } } return 0; } void update() { 
    int x=ed; while(x!=st){ 
    int i=pre[x]; edge[i]-=incf[ed]; edge[i^1]+=incf[ed]; x=ver[i^1]; } maxflow+=incf[ed]; } int main() { 
    // freopen("in.txt","r",stdin); int t;scanf("%d",&t); while(t--) { 
    scanf("%d%d",&n,&m); tot=1; for(int i=1;i<=n;i++)e[i].clear(),ee[i].clear(); memset(mp,0,sizeof(mp));//mp记录x-y的最小距离 memset(num,0,sizeof(num));//num记录的是mp[x][y]相同的路径数 memset(head,0,sizeof(head)); for(int i=1;i<=m;i++) { 
    int x,y,z;scanf("%d%d%d",&x,&y,&z); if(!mp[x][y]) { 
    e[x].push_back(y);//e记录正图 mp[x][y]=z; ee[y].push_back(x);//ee记录反图 num[x][y]=1; } else if(mp[x][y]>z)mp[x][y]=z,num[x][y]=1; else if(mp[x][y]==z)num[x][y]++; } scanf("%d%d",&st,&ed); dij1(); dij2(); for(int x=1;x<=n;x++) for(int i=0;i<e[x].size();i++)//判断加边的条件 { 
    int y=e[x][i],z=mp[x][y]; if(d[x]+dd[y]+z==d[ed])add(x,y,num[x][y]); } maxflow=0; while(bfs())update(); printf("%d\n",maxflow); } return 0; }