目录

1. Dijkstra解法

2. Bellman-Ford解法

3. SPFA解法

4. Dijkstra解法AC代码

5. Bellman-Ford解法AC代码

6. SPFA解法AC代码

1. Dijkstra解法

这题不仅涉及到基础的解法，还涉及到第二标准(累计军队数量)，以及还要记录最短路径条数。这些都是在绷紧路径的if语句中修改，我认为自己在这里的嵌套判断写法(先判断该结点是否已被访问过再进行下一步)比书上的复合条件句要清楚

//绷紧路径
for(int j=0;j<city[minC].nbr.size();j++){int nbr = city[minC].nbr[j].no;if(vis[nbr]==0){if(d[minC]+city[minC].nbr[j].dis<d[nbr]){n[nbr] = n[minC];d[nbr] = d[minC]+city[minC].nbr[j].dis;t[nbr] = t[minC] + city[nbr].teamN;}else if(d[minC]+city[minC].nbr[j].dis==d[nbr]){n[nbr] += n[minC];if(t[minC] + city[nbr].teamN > t[nbr])t[nbr] = t[minC] + city[nbr].teamN;}}
}	

对于起点的初始化，有三个条件就要初始化三个

//将起点的距离设置为0 
d[sCity] = 0;
//将起点的最短路径条数设置为1
n[sCity] = 1;
//将起点的军队数目设置为自身所有
t[sCity] = city[sCity].teamN;

值得注意的是最短路径条数的更新，如果有优化方案，当前结点的最短路径数目应该赋值为前驱结点的最短路径数目而不是1，如果有同样优的方案，当前结点的最短路径数目应该增加前驱结点的最短路径数目而不是加1。

2. Bellman-Ford解法

BF算法可以判断有没有可达负环，但是在这题的背景下用不到。它主要分为紧绷部分和判断负环部分。同样棘手的是最短路径的条数怎么办，当遇到可以紧绷时，直接用前驱的路径条数更新后继节点的，这个和Dijkstra一样，但是当遇到同优策略时，就不一样了，起初我也不会，看了参考书明白。需要设置一个前趋结点表set<int> pre[maxn]，如果遇到同优路径，先把当前前驱结点加入，然后把当前结点的最短路径数清零(非常容易忘)，对前驱结点集合进行遍历，所有前驱结点的最短路径条数之和就是当前结点的最短路径条数。此外，遇到更优路径的时候，需要先把前驱结点集合清空，再插入当前前驱结点。

注意：初始化是否完备，根据题意逻辑处理是否正确，BF不需要vis[maxn]数组

				int v = G[u][j].v;//v是u的邻接节点if(d[v]>d[u]+G[u][j].w){d[v] = d[u]+G[u][j].w;h[v] = h[u]+H[v];pre[v].clear();pre[v].insert(u);n[v] = n[u];}else if(d[v]==d[u]+G[u][j].w){pre[v].insert(u);n[v] = 0;for(set<int>::iterator it = pre[v].begin();it!=pre[v].end();it++){n[v] += n[*it];}if(h[v]<h[u]+H[v])h[v] = h[u]+H[v]; } 

3. SPFA解法

这里用的是BFS版本的SPFA，利用的规律是“d[u]变，只有u的后继节点的最短路径才有可能改变”，所以在进行一次优化以后(不管是第一尺度还是第二尺度)，才把当前优化过的结点放进队列中。至于数目的更新，由于这其实是改进的BF算法，和BF是一样的。

if(d[v]>d[u]+dis){d[v] = d[u]+dis;h[v] = h[u]+H[v];pre[v].clear();pre[v].insert(u);n[v] = n[u];if(inq[v]==false){Q.push(v);inq[v] = true;num[v] ++;if(num[v]>=vNum)return false;}
}else if(d[v]==d[u]+dis){pre[v].insert(u);n[v] = 0;for(set<int>::iterator it = pre[v].begin();it!=pre[v].end();it++){n[v]+=n[*it];}if(h[v]<h[u]+H[v])h[v] = h[u]+H[v];if(inq[v]==false){Q.push(v);inq[v] = true;num[v] ++;if(num[v]>=vNum)return false;}
}

4. Dijkstra解法AC代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;const int INF = 1000000000;//10的9次方 
const int maxn = 510;
const double eps = 1e-3;struct Node{int no;int dis;Node(int _no,int _dis):no(_no),dis(_dis){}};struct City{vector<Node> nbr;int teamN;
}city[maxn];int cityN,roadN,sCity,dCity;bool vis[maxn] = {0};
int d[maxn]; 
int t[maxn] = {0};//数组t存放的是最短路径上累积的最大救援队数
int n[maxn] = {0};//n存放最短路径的数量void Dijkstra(){//填充最短距离路径数组(其他三个都初始化过了)fill(d,d+cityN,INF);//将起点的距离设置为0 d[sCity] = 0;//将起点的最短路径条数设置为1n[sCity] = 1;//将起点的军队数目设置为自身所有t[sCity] = city[sCity].teamN;	for(int i=0;i<cityN;i++){//每一次访问一个结点 //找到距离当前数组距离最小的数组int minD = INF,minC  = -1;//最短距离和对应城市编号for(int j=0;j<cityN;j++){if(d[j]<minD&&vis[j]==0){minD = d[j];minC = j;} } if(minC==-1)return;//说明所有结点都加入了S else vis[minC] = 1;//绷紧路径for(int j=0;j<city[minC].nbr.size();j++){int nbr = city[minC].nbr[j].no;if(vis[nbr]==0){if(d[minC]+city[minC].nbr[j].dis<d[nbr]){n[nbr] = n[minC];d[nbr] = d[minC]+city[minC].nbr[j].dis;t[nbr] = t[minC] + city[nbr].teamN;}else if(d[minC]+city[minC].nbr[j].dis==d[nbr]){n[nbr] += n[minC];if(t[minC] + city[nbr].teamN > t[nbr])t[nbr] = t[minC] + city[nbr].teamN;}}}		 }	
}int main(){scanf("%d %d %d %d",&cityN,&roadN,&sCity,&dCity);//读入每个城市救援队的数量 for(int i=0;i<cityN;i++){scanf("%d",&city[i].teamN);}//读入每一条路的长度for(int i=0;i<roadN;i++){int c1,c2,len;scanf("%d %d %d",&c1,&c2,&len);Node* n1 = new Node(c1,len);city[c2].nbr.push_back(*n1);Node* n2 = new Node(c2,len);city[c1].nbr.push_back(*n2);}//调用Dijkstra算法Dijkstra(); printf("%d %d\n",n[dCity],t[dCity]); return 0; 
}

5. Bellman-Ford解法AC代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<cstring>using namespace std;const int maxn = 510;
const int SUP = 2000000000;struct Node{int v,w;Node(int _v,int _w):v(_v),w(_w){}
};vector<Node> G[maxn];int H[maxn];//各个城市固有帮手数量 
int d[maxn];
int h[maxn] = {0};//从源点到某地最多的帮手数量
int n[maxn] = {0};//到达某地的最短路径数 int vNum;set<int> pre[maxn];bool Bellman(int so){fill(d,d+vNum,SUP);d[so] = 0;h[so] = H[so];n[so] = 1;for(int i=0;i<vNum-1;i++){for(int u=0;u<vNum;u++){for(int j=0;j<G[u].size();j++){int v = G[u][j].v;//v是u的邻接节点if(d[v]>d[u]+G[u][j].w){d[v] = d[u]+G[u][j].w;h[v] = h[u]+H[v];pre[v].clear();pre[v].insert(u);n[v] = n[u];}else if(d[v]==d[u]+G[u][j].w){pre[v].insert(u);n[v] = 0;for(set<int>::iterator it = pre[v].begin();it!=pre[v].end();it++){n[v] += n[*it];}if(h[v]<h[u]+H[v])h[v] = h[u]+H[v]; } }}}for(int u=0;u<vNum;u++){for(int j=0;j<G[u].size();j++){int v = G[u][j].v;if(d[v]>d[u]+G[u][j].w)return false;}}return true;
}int main(){int eNum,so,de;scanf("%d %d %d %d",&vNum,&eNum,&so,&de); for(int i=0;i<vNum;i++){scanf("%d",&H[i]);}int v1,v2,w;for(int i=0;i<eNum;i++){scanf("%d %d %d",&v1,&v2,&w);Node node = Node(v2,w);G[v1].push_back(node);node = Node(v1,w);G[v2].push_back(node);}Bellman(so);printf("%d %d",n[de],h[de]);return 0;
}

6. SPFA解法AC代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<cstring>using namespace std;const int maxn = 510;
const int SUP = 2000000000;struct Node{int v,w;Node(int _v,int _w):v(_v),w(_w){}
};vector<Node> G[maxn];int H[maxn];//各个城市固有帮手数量 
int d[maxn];
int h[maxn] = {0};//从源点到某地最多的帮手数量
int n[maxn] = {0};//到达某地的最短路径数 
int num[maxn] = {0};//各个点入队次数 int vNum;set<int> pre[maxn];bool SPFA(int so){fill(d,d+vNum,SUP);d[so] = 0;n[so] = 1;h[so] = H[so];bool inq[maxn] = {0};queue<int> Q;Q.push(so);inq[so] = true;while(!Q.empty()){int u = Q.front();Q.pop();inq[u] = false;for(int i=0;i<G[u].size();i++){int v = G[u][i].v;int dis = G[u][i].w;if(d[v]>d[u]+dis){d[v] = d[u]+dis;h[v] = h[u]+H[v];pre[v].clear();pre[v].insert(u);n[v] = n[u];if(inq[v]==false){Q.push(v);inq[v] = true;num[v] ++;if(num[v]>=vNum)return false;}}else if(d[v]==d[u]+dis){pre[v].insert(u);n[v] = 0;for(set<int>::iterator it = pre[v].begin();it!=pre[v].end();it++){n[v]+=n[*it];}if(h[v]<h[u]+H[v])h[v] = h[u]+H[v];if(inq[v]==false){Q.push(v);inq[v] = true;num[v] ++;if(num[v]>=vNum)return false;}}}}return true;
}int main(){int eNum,so,de;scanf("%d %d %d %d",&vNum,&eNum,&so,&de); for(int i=0;i<vNum;i++){scanf("%d",&H[i]);}int v1,v2,w;for(int i=0;i<eNum;i++){scanf("%d %d %d",&v1,&v2,&w);Node node = Node(v2,w);G[v1].push_back(node);node = Node(v1,w);G[v2].push_back(node);}SPFA(so);printf("%d %d",n[de],h[de]);return 0;
}