这里给个 spfa算法的题解
SPFA 算法被卡了，大部分人写的都是 dijkstra算法，这里提供一个SPFA 的思路
-
单元最短路径模板转化
思路分析： 首先 spfa 算法 求的是单源最短路径 ，也就是 说 从 1个点 到 其他 N个点的最短路径， 先用 spfa 算法 预处理出 出发点 到 其他点的最短路径， a,b,c,d,e 5个点到其他各个点的最短路径 -
用 DFS 暴搜 序列次序， 最终 可以获得 全局时间最少的一个序列【由于只有5个点，这里也可以用状态压缩 DP ，二进制来表示序列】
#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
#include <cstring>
#include <unordered_map>
using namespace std;
const int MAXN = 50000 +10, MAXM = 1e5+10,MAXT = 100+10,INF = 0x3f3f3f3f;
int n,m;
int source[6];
int dist[7][MAXN];
unordered_map<int,vector<pair<int,int> >> path;
void spfa(int start,int no) {
queue<int> q;
unordered_set<int> inq;
memset(dist[no],0x3f,sizeof dist[no]);
dist[no][start] = 0;
q.push(start);
inq.insert(start);
while(q.size()) {
int u = q.front();q.pop();
inq.erase(u);
for(auto &temp:path[u]) {
int v = temp.first, cost = temp.second;
if(dist[no][v] > dist[no][u] + cost) {
dist[no][v] = cost + dist[no][u];
if(inq.count(v)==0) {
inq.insert(v);
q.push(v);
}
}
}
}
}
bool inset[MAXN];
int dfs(int cnt,int start,int total_dist) {
if(cnt == 6) {
return total_dist;
}
int res = INF;
for(int i=1;i<=5;++i) {
if(!inset[i]) {
inset[i] = true;
res = min(res,dfs(cnt+1,i,total_dist + dist[start][source[i]]));
inset[i] = false;
}
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=5;++i) cin>> source[i];//亲戚在的车站
source[0] = 1;
while (m -- ) {
int x,y,d;
cin>> x>>y >>d;
path[x].push_back({y,d});
path[y].push_back({x,d});
}
for(int i=0;i<=5;++i) {
spfa(source[i],i );
}
cout << dfs(1,0,0) <<endl;
return 0;
}
最终代码 【dfs + dijkstra 算法 】
#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
#include <cstring>
#include <unordered_map>
using namespace std;
const int MAXN = 50000 +10, MAXM = 1e5+10,MAXT = 100+10,INF = 0x3f3f3f3f;
int n,m;
int source[6];
int dist[7][MAXN];
unordered_map<int,vector<pair<int,int> >> path;
void spfa(int start,int no) {
queue<int> q;
unordered_set<int> inq;
memset(dist[no],0x3f,sizeof dist[no]);
dist[no][start] = 0;
q.push(start);
inq.insert(start);
while(q.size()) {
int u = q.front();q.pop();
inq.erase(u);
for(auto &temp:path[u]) {
int v = temp.first, cost = temp.second;
if(dist[no][v] > dist[no][u] + cost) {
dist[no][v] = cost + dist[no][u];
if(inq.count(v)==0) {
inq.insert(v);
q.push(v);
}
}
}
}
}
void dijkstra(int num,int start_point) {
struct State{
int dist,point;
bool operator < (const State&w) const {
// q默认大根堆，这样小的会排前面
return dist > w.dist;
}
};
priority_queue<State > q;
q.push({ 0, start_point});
memset(dist[num],0x3f,sizeof dist[num]);
dist[num][start_point] = 0;
while(q.size()) {
auto ts = q.top();q.pop();
int u = ts.point;
for(auto &temp: path[u]) {
int v = temp.first, ccost = temp.second;
if(dist[num][v] > dist[num][u] + ccost) {
dist[num][v] = dist[num][u] + ccost;
q.push({dist[num][v],v});
//松弛操作
}
}
}
}
bool inset[MAXN];
int dfs(int cnt,int start,int total_dist) {
if(cnt == 6) {
return total_dist;
}
int res = INF;
for(int i=1;i<=5;++i) {
if(!inset[i]) {
inset[i] = true;
res = min(res,dfs(cnt+1,i,total_dist + dist[start][source[i]]));
inset[i] = false;
}
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=5;++i) cin>> source[i];//亲戚在的车站
source[0] = 1;
while (m -- ) {
int x,y,d;
cin>> x>>y >>d;
path[x].push_back({y,d});
path[y].push_back({x,d});
}
for(int i=0;i<=5;++i) {
//0 次，从 1出发
dijkstra(i,source[i]);
//spfa(source[i],i );
}
cout << dfs(1,0,0) <<endl;
return 0;
}
状态压缩DP 解法
举个例子： 就是将 二进制串表示 序列
比如 0001 表示选择了 第1 位，
1001 表示 选择了 第1,4位
把二进制看成一个序列，由于题目不要求序列顺序，只要求最小值，完全可以不用 DFS ，用 DP 就可以了 【不用管顺序】
#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
#include <cstring>
#include <unordered_map>
using namespace std;
const int MAXN = 50000 +10, MAXM = 1e5+10,MAXT = 100+10,INF = 0x3f3f3f3f , MAX_STATE = 1<<5;
int n,m;
int source[6];
int dist[7][MAXN];
int dp[5][MAX_STATE];
unordered_map<int,vector<pair<int,int> >> path;
/*
void spfa(int start,int no) {
queue<int> q;
unordered_set<int> inq;
memset(dist[no],0x3f,sizeof dist[no]);
dist[no][start] = 0;
q.push(start);
inq.insert(start);
while(q.size()) {
int u = q.front();q.pop();
inq.erase(u);
for(auto &temp:path[u]) {
int v = temp.first, cost = temp.second;
if(dist[no][v] > dist[no][u] + cost) {
dist[no][v] = cost + dist[no][u];
if(inq.count(v)==0) {
inq.insert(v);
q.push(v);
}
}
}
}
}
*/
void dijkstra(int num,int start_point) {
struct State{
int dist,point;
bool operator < (const State&w) const {
// q默认大根堆，这样小的会排前面
return dist > w.dist;
}
};
priority_queue<State > q;
q.push({ 0, start_point});
dist[num][start_point] = 0;
while(q.size()) {
auto ts = q.top();q.pop();
int u = ts.point;
for(auto &temp: path[u]) {
int v = temp.first, ccost = temp.second;
if(dist[num][v] > dist[num][u] + ccost) {
dist[num][v] = dist[num][u] + ccost;
q.push({dist[num][v],v});
//松弛操作
}
}
}
}
/*
bool inset[MAXN];
int dfs(int cnt,int start,int total_dist) {
if(cnt == 6) {
return total_dist;
}
int res = INF;
for(int i=1;i<=5;++i) {
if(!inset[i]) {
inset[i] = true;
res = min(res,dfs(cnt+1,i,total_dist + dist[start][source[i]]));
inset[i] = false;
}
}
return res;
}
*/
int main()
{
cin>>n>>m;
for(int i=1;i<=5;++i) cin>> source[i];//亲戚在的车站
source[0] = 1;
memset(dist ,0x3f,sizeof dist );
//记得dp设置 无穷大
memset(dp,0x3f,sizeof dp);
while (m -- ) {
int x,y,d;
cin>> x>>y >>d;
path[x].push_back({y,d});
path[y].push_back({x,d});
}
//从 第1个车站触发 ，计算的记录 在 dist[0] 里面
dijkstra(0,1);
for(int i=1;i<=5;++i)
// 拜访 第 1 位 亲戚的状态 【要拜访的 第1位亲戚 从 a,b,c,d,e 5个地方挑选一个最短的】
dp[i-1][1<<(i-1)] = dist[0][source[i]];
for(int i=1;i<=5;++i) {
//拜访 剩下的 5个亲戚
dijkstra(i,source[i]);
}
for(int i=1;i< MAX_STATE;++i) {
for(int j=0;j<5;++j) {
if(i >>j & 1) continue;
for(int k=0;k<5;++k) {
if(i>>k & 1) {
dp[j][i|(1<<j)] = min(dp[j][i|(1<<j)],dp[k][i] + dist[k+1][source[j+1]]);
}
}
}
}
int res = INF;
for(int i=0;i<5;++i)
res = min(res, dp[i][MAX_STATE-1]);/* ,printf("res:=%d\n",res);*/
//cout << dfs(1,0,0) <<endl;
cout << res <<endl;
//for(int i=0;i<5;++i)
// cout << dp[i][1]<<endl;
return 0;
}
