dp是特殊的最短路,是无环图(拓扑图)上的最短路问题
1137. 选择最佳线路
1137. 选择最佳线路 - AcWing题库
// 反向建图就行
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10, M = 2e4 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s;
int a[N];
int dis[N]; bool st[N];
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII>> q;
memset(dis, 0x3f, sizeof(dis));
memset(st, 0, sizeof(st));
dis[s] = 0;
q.push({ dis[s], s });
while (q.size())
{
auto t = q.top(); q.pop();
int x = t.second, d = t.first;
if (st[x]) continue;
st[x] = true;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[y] > d + w[i])
{
dis[y] = d + w[i];
q.push({ dis[y], y });
}
}
}
}
int main()
{
while (~scanf("%d%d%d", &n, &m, &s))
{
idx = 0;
memset(h, -1, sizeof(h));
int x, y, d;
while ( m -- )
{
scanf("%d%d%d", &x, &y, &d);
add(y, x, d);
}
int wn;
scanf("%d", &wn);
for (int i = 1; i <= wn; ++ i ) scanf("%d", &a[i]);
dijkstra();
int res = 0x3f3f3f3f;
for (int i = 1; i <= wn; ++ i ) res = min(res, dis[a[i]]);
if (res == 0x3f3f3f3f) puts("-1");
else printf("%d\n", res);
}
return 0;
}
对于每组测试数据,该重置的数据要重置,我没有重置idx,导致TLE
处理反向建图,还有一种扩展做法:虚拟源点
设置虚拟源点,与每个起点之间连接边权为0的边
原问题:从多个源点出发,到达终点的最短路径
先问题:从虚拟源点出发,到达终点的最短路径
两者的最短路径一一对应,并且路径和相同
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10, M = 3e4 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s;
int a[N];
int dis[N]; bool st[N];
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII>> q;
memset(dis, 0x3f, sizeof(dis));
memset(st, 0, sizeof(st));
dis[0] = 0;
q.push({ dis[0], 0 });
while (q.size())
{
auto t = q.top(); q.pop();
int x = t.second, d = t.first;
if (st[x]) continue;
st[x] = true;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[y] > d + w[i])
{
dis[y] = d + w[i];
q.push({ dis[y], y });
}
}
}
}
int main()
{
while (~scanf("%d%d%d", &n, &m, &s))
{
idx = 0;
memset(h, -1, sizeof(h));
int x, y, d;
while ( m -- )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d);
}
int wn;
scanf("%d", &wn);
for (int i = 1; i <= wn; ++ i )
{
scanf("%d", &a[i]);
add(0, a[i], 0); // 设置虚拟源点
}
dijkstra();
if (dis[s] == 0x3f3f3f3f) puts("-1");
else printf("%d\n", dis[s]);
}
return 0;
}
debug:将虚拟源点与起点之间建立边,要注意M的大小是否足够,又是M开小了…
1131. 拯救大兵瑞恩
1131. 拯救大兵瑞恩 - AcWing题库
从集合的角度分析
状态表示:
集合:起点为左上角,终点为图中任意一点的所有路径,用
f
(
x
,
y
)
f(x, y)
f(x,y)表示终点为
[
x
,
y
]
[x, y]
[x,y]的路径
属性:最小时间(路径和)
所以
f
(
x
,
y
)
f(x, y)
f(x,y)表示终点为
[
x
,
y
]
[x, y]
[x,y]的最小路径和
但是图中存在无法通过的墙以及需要钥匙打开的门,所以用两个维度表示路径将无法更新集合
考虑增加一个维度
s
t
a
t
e
state
state,状态压缩,表示拥有的钥匙状态
即
f
(
x
,
y
,
s
t
a
t
e
)
f(x, y, state)
f(x,y,state)表示拥有钥匙的状态为
s
t
a
t
e
state
state时,递达
[
x
,
y
]
[x, y]
[x,y]的最短路
状态计算:
如何划分
f
(
x
,
y
,
s
t
a
t
e
)
f(x, y, state)
f(x,y,state)?一般的dp问题是从后往前考虑,图论中的集合分析一般从前往后考虑
即
f
(
x
,
y
,
s
t
a
t
e
)
f(x, y, state)
f(x,y,state)能推导出哪些集合?
若
[
x
,
y
]
[x, y]
[x,y]有钥匙,可以捡起这些钥匙,假设钥匙的状态为key,那么状态推导就是
f
(
x
,
y
,
s
t
a
t
e
)
−
>
f
(
x
,
y
,
s
t
a
t
e
∣
k
e
y
)
f(x, y, state)->f(x, y, state | key)
f(x,y,state)−>f(x,y,state∣key)
若
[
x
,
y
]
[x, y]
[x,y]无钥匙,那么可以向相邻的位置走,
f
(
x
,
y
,
s
t
a
t
e
)
−
>
f
(
n
x
,
n
y
,
s
t
a
t
e
)
f(x, y, state)->f(nx, ny, state)
f(x,y,state)−>f(nx,ny,state),此时的最短距离要+1
由于这个问题中存在环路,所以无法用dp更新集合,只能用最短路算法更新集合
这题比较麻烦的是:建边,相邻两个位置若没有墙,那么可以建立一条权值为1的边
如何表示两个二维坐标之间有边?这里涉及到二维坐标到一维的转换,然后用邻接表存储图
若两个位置之间存在门,用边权表示门的种类,但是实际的边权为1
若两个位置之间既不存在门,也不存在墙,那么创建一条权值为0的边,但时间的边权为1。所以
w
[
i
]
w[i]
w[i]为非0表示这个边上有道门,为0表示可以直接通过
对于墙的情况,直接忽略,不建立边(表示不连通)即可
用set存储已经建立的边,防止重复建边
#include <iostream>
#include <cstring>
#include <deque>
#include <set>
using namespace std;
typedef pair<int, int> PII;
const int N = 11, P = 1 << N;
const int M = 400;
int h[N * N], e[M], ne[M], w[M], idx;
int g[N][N]; // 二维到一维的转换
int key[N * N]; // 每个坐标的钥匙状态
int dis[N * N][P]; bool st[N * N][P];
set<PII> s;
int n, m, p, k;
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
void build()
{
int dx[4] = { 0, 1, 0, -1}, dy[4] = { 1, 0, -1, 0 };
for (int x = 1; x <= n; ++ x )
for (int y = 1; y <= m; ++ y )
for (int i = 0; i < 4; ++ i )
{
int nx = x + dx[i], ny = y + dy[i];
if (nx > 0 && nx <= n && ny > 0 && ny <= m)
{
int a = g[x][y], b = g[nx][ny];
if (!s.count({a, b})) add(a, b, 0);
}
}
}
int bfs()
{
memset(dis, 0x3f, sizeof(dis));
deque<PII> q;
dis[1][0] = 0;
q.push_back({1, 0});
while (q.size())
{
auto t = q.front(); q.pop_front();
int x = t.first, state = t.second;
if (st[x][state]) continue;
st[x][state] = true;
if (x == n * m) return dis[n * m][state];
if (key[x])
{
int nstate = state | key[x];
if (dis[x][nstate] > dis[x][state])
{
dis[x][nstate] = dis[x][state];
q.push_front({x, nstate});
}
}
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (w[i] && !((state >> w[i]) & 1)) continue;
if (dis[y][state] > dis[x][state] + 1)
{
dis[y][state] = dis[x][state] + 1;
q.push_back({y, state});
}
}
}
return -1;
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d%d%d", &n, &m, &p, &k);
int cnt = 1;
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= m; ++ j )
g[i][j] = cnt ++ ;
int x1, y1, x2, y2, x, y, d;
while ( k -- )
{
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &d);
x = g[x1][y1], y = g[x2][y2];
s.insert({x, y}), s.insert({y, x});
if (d) add(x, y, d), add(y, x, d);
}
build(); // 建立除了门和墙的边
int l;
scanf("%d", &l);
while ( l -- )
{
scanf("%d%d%d", &x, &y, &d);
key[g[x][y]] |= 1 << d;
}
printf("%d\n", bfs());
return 0;
}
debug:int x = t.first, state = t.second
写成int x = t.secnd, state = t.first
只能说是dijkstra写多了
1134. 最短路计数
1134. 最短路计数 - AcWing题库
从集合的角度考虑,
f
(
i
)
f(i)
f(i)表示图中第i个点的最短路条数,假设与i相连的点由k个,那么
f
(
i
)
=
f
(
s
1
)
+
f
(
s
2
)
+
.
.
.
+
f
(
s
k
)
f(i) = f(s_1) + f(s_2) + ... + f(s_k)
f(i)=f(s1)+f(s2)+...+f(sk),第i个点的最短路条数由与之直接相连的点的最短路条数累加而成
那么要求解
f
(
i
)
f(i)
f(i),就要先算出它的子集,但是图论问题可能存在环,无法确定
f
(
i
)
f(i)
f(i)是否会影响它的子集。所以只能在拓扑图中才能这样更新集合,考虑最短路算法的更新是否具有拓扑序
三种求最短路的方法:1.BFS 2.Dijkstra 3.Bellman-ford
探讨它们求解最短路时,是否具有拓扑序?
对于BFS,由于每个点只会入队一次且只会出队一次,说明BFS的更新天然地具有拓扑序,因为出队的点不会被后续入队的点影响
对于Dijkstra,由于每个点会入队多次,但只会出队一次,也说明了Dijkstra的更新天然地具有拓扑序
对于spfa,由于它是暴力算法的优化,每个点都会入队与出队多次,所以spfa的更新不具有拓扑序,已经出队(更新完成)的点可能影响被后续入队的点影响
即bfs和dijkstra的更新是一颗最短路树,而spfa的更新不是一颗最短路树
统计最短路条数时,可以遍历最短路树
若统计i节点的最短路条数,只需要累乘父节点的数量即可
而spfa的更新不具有拓扑序,即不存在最短路树,要是图中存在负权边,无法使用天然具有拓扑序的bfs和dijkstra时,只能先用spfa求出最短路,维护出最短路树,再求最短路条数
一般情况下,图中不能存在权值为0的点,否则无法建立出最短路树,因为达到某一个点的最短路不能确定
这题直接用bfs更新最短路,在更新过程中完成最短路条数的统计:用x更新y时,dis[y] > dis[x] + 1
时,y的最短路数量等于x的最短路数量
若dis[y] == dix[x] + 1
,y的最短路条数等于两者的数量累加
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 4e5 + 10, mod = 100003;
int h[N], e[M], ne[M], idx;
int dis[N], q[N], hh, tt = -1;
int cnt[N];
int n, m;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
void bfs()
{
memset(dis, 0x3f, sizeof(dis));
q[++ tt ] = 1;
dis[1] = 0, cnt[1] = 1;
while (tt >= hh)
{
int x = q[hh ++ ];
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[y] > dis[x] + 1)
{
dis[y] = dis[x] + 1;
q[++ tt ] = y;
cnt[y] = cnt[x];
}
else if(dis[y] == dis[x] + 1) cnt[y] = (cnt[y] + cnt[x]) % mod;
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
int x, y;
while ( m -- )
{
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
bfs();
for (int i = 1; i <= n; ++ i )
{
if (cnt[i] == 0x3f3f3f3f) puts("0");
else printf("%d\n", cnt[i]);
}
return 0;
}
383. 观光
383. 观光 - AcWing题库
由于无负权边,所以用dijkstra更新最短路,同时维护最短路条数
但是题目还要维护最短路条数,所以这里用了个类似拯救大兵瑞恩的思想:状压dis[i][0]
表最短路距离,dis[i][1]
表示次短路距离,由于次短路的更新也具有拓扑序,所以我们可以在更新次短路的时候维护次短路条数文章来源:https://www.toymoban.com/news/detail-626220.html
d
i
s
[
i
]
[
1
]
dis[i][1]
dis[i][1]如何计算?与i相连的所有点的最短路以及次短路中,第二大的数
代码体现在:
若dis[y][0] > dis[x][0] + w[i]
,则更新最短路
d
i
s
[
y
]
[
0
]
dis[y][0]
dis[y][0],那么最短路成为次短路
d
i
s
[
y
]
[
1
]
dis[y][1]
dis[y][1],更新次短路,同时更新最短路
若dis[y][0] == dis[x][0] + w[i]
,那么最短路条数累加,cnt[y][0] += cnt[x][0]
若dis[y][1] > dis[x][0] + w[i]
,那么更新次短路
d
i
s
[
y
]
[
1
]
dis[y][1]
dis[y][1]
若dis[y][1] == dis[x][0] + w[i]
,那么次短路条数累加,cnt[y][1] += cnt[x][1]
文章来源地址https://www.toymoban.com/news/detail-626220.html
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s, t;
int dis[N][2], cnt[N][2]; bool st[N][2];
struct Ver
{
int x, d, type;
bool operator>(const Ver& v) const // 建小堆重载>
{
return d > v.d;
}
};
void add(int x, int y, int d)
{
e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}
int dijkstra()
{
memset(dis, 0x3f, sizeof(dis));
memset(st, 0, sizeof(st));
memset(cnt, 0, sizeof(cnt));
priority_queue<Ver, vector<Ver>, greater<Ver>> q;
q.push({s, 0, 0});
dis[s][0] = 0, cnt[s][0] = 1;
while (q.size())
{
auto t = q.top(); q.pop();
int x = t.x, d = t.d, type = t.type;
int count = cnt[x][type];
if (st[x][type]) continue;
st[x][type] = true;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (dis[y][0] > d + w[i])
{
dis[y][1] = dis[y][0], cnt[y][1] = cnt[y][0];
q.push({y, dis[y][1], 1});
dis[y][0] = d + w[i], cnt[y][0] = count;
q.push({y, dis[y][0], 0});
}
else if (dis[y][0] == d + w[i]) cnt[y][0] += count;
else if(dis[y][1] > d + w[i])
{
dis[y][1] = d + w[i], cnt[y][1] = count;
q.push({y, dis[y][1], 1});
}
else if (dis[y][1] == d + w[i]) cnt[y][1] += count;
}
}
int res = cnt[t][0];
if (dis[t][0] + 1== dis[t][1]) res += cnt[t][1];
return res;
}
int main()
{
int T;
scanf("%d", &T);
while ( T -- )
{
idx = 0;
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
int x, y, d;
while ( m -- )
{
scanf("%d%d%d", &x, &y, &d);
add(x, y, d);
}
scanf("%d%d", &s, &t);
printf("%d\n", dijkstra());
}
return 0;
}
到了这里,关于第三章 图论 No.2单源最短路之虚拟源点,状压最短路与最短路次短路条数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!