临沂h5建站,中国企业500强厉害吗,11电影网,西安网站设计锦文章目录 1137. 选择最佳线路1131. 拯救大兵瑞恩1134. 最短路计数383. 观光 dp是特殊的最短路#xff0c;是无环图#xff08;拓扑图#xff09;上的最短路问题 1137. 选择最佳线路
1137. 选择最佳线路 - AcWing题库
// 反向建图就行
#include iostream
#include… 文章目录 1137. 选择最佳线路1131. 拯救大兵瑞恩1134. 最短路计数383. 观光 dp是特殊的最短路是无环图拓扑图上的最短路问题 1137. 选择最佳线路
1137. 选择最佳线路 - AcWing题库
// 反向建图就行
#include iostream
#include queue
#include cstring
using namespace std;typedef pairint, 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_queuePII, vectorPII, greaterPII 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 pairint, 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_queuePII, vectorPII, greaterPII 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 pairint, 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];
setPII 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));dequePII 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;
}debugint 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] 1y的最短路条数等于两者的数量累加
#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]表示次短路距离由于次短路的更新也具有拓扑序所以我们可以在更新次短路的时候维护次短路条数 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]
#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_queueVer, vectorVer, greaterVer 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;
}
