题目类型 搜索题 (最短路 + dp)
题目意思
给出 n 个点 m 条边 ( 1 <= n, m <= 10)
其中 每条边由 5 个变量 Ai, Bi, Ci ,Pi, Ri 描述 表示从 Ai 到 Bi 如果到达 Ai 时经过了 Ci 的话就需要花费 Pi 如果没经过 ci的话就花费 Ri
现在问从 1 到 n 最少花费
解题方法
SPFA + 状态压缩dp
用数组 dp[i][j] 表示 到达 i 的时候经过了点集 j 的最少花费
然后结合 SPFA 的求解过程, 根据 点集中是否存在 Ci 判断边的花费 最终可扫描一次 dp[n][0] -> dp[n][(1<<n)-1] 找出最优解 (具体看代码)
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 1<<30;
int dp[20][1100];
int n;
vector<int>M[20];
vector<int>J[20];
vector<int>P[20];
vector<int>R[20];
void SPFA() {
for( int i=1; i<=n; i++ ) for( int j=0; j<(1<<n); j++ ) dp[i][j] = INF;
dp[1][1] = 0;
queue<int>q;
q.push(1);
bool vis[20];
memset(vis, 0, sizeof(vis));
vis[1] = 1;
while(!q.empty()) {
int f = q.front(); q.pop();
vis[f] = 0;
for( int i=0; i<M[f].size(); i++ ) { // 更新与 f 相邻的点
int v = M[f][i];
int c = J[f][i];
for( int j=0; j<(1<<n); j++ ) { // 用 dp[f][j] 去更新其他状态
if((j & (1<<(f-1)))==0) continue;
if((j & (1<<(c-1)))) { // 如果经过了 c 花费就是 P[f][i]
if(dp[v][j|(1<<(v-1))] > dp[f][j] + P[f][i]) {
dp[v][j|(1<<(v-1))] = dp[f][j] + P[f][i];
if(vis[v] == 0) {
q.push(v);
vis[v] = 1;
}
}
}
else { // 否则花费是 R[f][i]
if(dp[v][j|(1<<(v-1))] > dp[f][j] + R[f][i]) {
dp[v][j|(1<<(v-1))] = dp[f][j] + R[f][i];
if(vis[v] == 0) {
q.push(v);
vis[v] = 1;
}
}
}
}
}
}
}
int main() {
//freopen("in", "r", stdin);
int m;
while(scanf("%d%d", &n, &m) != EOF) {
for( int i=0; i<m; i++ ) {
int a, b, c, p, r;
scanf("%d%d%d%d%d", &a, &b, &c, &p, &r);
M[a].push_back(b);
J[a].push_back(c);
P[a].push_back(p);
R[a].push_back(r);
}
SPFA();
int ans = INF;
for( int i=0; i<(1<<n); i++ ) {
if((i & 1) && (i & (1<<(n-1)))) {
ans = min(ans, dp[n][i]);
}
}
if(ans == INF) printf("impossible\n");
else printf("%d\n", ans);
}
return 0;
}