首页 > 其他分享 >【学习笔记】最短路

【学习笔记】最短路

时间：2024-07-27 21:41:30浏览次数：13  
标签：松弛 int 短路 笔记 学习 vis push dis

【学习笔记】最短路

前言：只是对一些最短路算法的实现整理。

以下内容有部分摘自OI_wiki。

Floyd 算法

求全源最短路。可以有负边权。

Floyd 算法的本质是动态规划。设 \(dis(k, i, j)\) 表示由若干个编号不超过 \(k\) 的节点中转后从 \(i\) 到 \(j\) 的最短路。

该“动规”有两个决策，一是经过编号不超过 \(k-1\) 的节点由 \(i\) 到 \(j\)，二是由 \(i\) 到 \(k\)，再由 \(k\) 到 \(j\)。两者取最小值，据此可写出转移方程：

\[dis(k, i, j) = \min(dis(k-1, i, j), dis(k-1, i, k)+dis(k-1,k, j)) \]

最终 \(i\) 到 \(j\) 的最短路为 \(dis(n, i, j)\)。

三维数组可能会爆内存，观察到 \(dis(k, i, j)\) 只与 \(k-1\) 层有关，故可以用滚动数组的方式将第一位滚去，此时的转移方程为：

\[dis(i, j) = min(dis(i, j), dis(i, k)+dis(k, j)) \]

最终 \(i\) 到 \(j\) 的最短路为 \(dis(i, j)\)。

时间复杂度为 \(O(n^3)\)，空间复杂度为 \(O(n^2)\)。

实现过程：

  1. 初始化 \(dis\) 数组所有值为正无穷。随后令 \(dis(i, j) = M(i, j)\)，\(M(i, j)\) 为邻接矩阵中的值，即 \(i\) 到 \(j\) 的边权。

  2. 三重循环跑一遍 Floyd。

代码主体部分实现：

for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);

Floyd 算法也可以在前 \(k\) 个元素的两两之间的最短路确定的时候加一点 \(k+1\)，以 \(O(k^2)\) 的时间复杂度更新两两节点之间的最短路。

CF295B Greg and Graph

正向思路是按照题意每次删除点 \(x_{i}\)，但 Floyd 不支持删除点，并且这样做会很麻烦：每到一个点 \(x_i\)，就要做一次复杂度为 \(O(n^3)\) 的 Floyd，整体复杂度为 \(O(n^4)\)，也会超时。

所以我们逆向思考，看成每次添加一个点 \(x_{i}\)，并记录该点出现过。在计算总和时特判这些点是否出现过，记录答案。最后倒序输出。时间复杂度为 \(O(n^3)\)。

Code 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 505;

int dis[N][N], del[N];
ll ans[N];
bool flag[N];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>dis[i][j];
    for(int i=1; i<=n; i++)
        cin>>del[i];
    for(int p=n; p>=1; p--){
        int k = del[p];
        flag[k] = 1;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
                if(flag[i] && flag[j]) ans[p] += dis[i][j];
            }
        }
    }
    for(int i=1; i<=n; i++)
        cout<<ans[i]<<" ";
    return 0;
}

传递闭包

给出若干个元素以及它们的两两关系，如果这些元素具有传递性，我们就可以推出尽可能多的元素之间的关系。

此时 \(dis(i, j)\) 数组的意义为 \((i, j)\) 是否具有关系，有关系则 \(dis(i, j) = 1\)，无关系则 \(dis(i, j) = 0\)。

转移方程为：

\[dis(i, j) = dis(i, j) \vee (dis(i, k) \wedge dis(k, j)) \]

具体解释为 \((i，j)\) 既可以经过不大于 \(k-1\) 的节点连通，也可以由 \(i\) 经过 \(k\) 中转到 \(j\) 来连通。

实现过程：

  1. 令 \(dis(i, i) = dis(i, j) = 1\)，满足自己到自己可达， \((i, j)\) 之间有关系（关系是 \(i\) 到 \(j\)）。\(dis\) 数组内其余均为 \(0\)。

  2. 三重循环跑一遍 Floyd。

代码主体部分实现：

for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dis[i][j] |= (dis[i][k] & dis[k][j]);

Dijkstra 算法

求解非负权图中单源最短路最稳定的算法。

实现过程：

将结点分成两个集合：已确定最短路长度的点集（记为 \(S\) 集合）的和未确定最短路长度的点集（记为 \(T\) 集合）。一开始所有的点都属于 \(T\) 集合。

  1. 初始化 \(dis(s)=0\)，其他点的 \(dis\) 均为 \(+\infty\)。

  2. 然后重复操作：

    从 \(T\) 集合中，选取一个最短路长度最小的结点，移到 \(S\) 集合中。对那些刚刚被加入 \(S\) 集合的结点的所有出边执行松弛操作。直到 \(T\) 集合为空，算法结束。

有多种方法来维护操作中最短路长度最小的结点，不同的实现导致了 Dijkstra 算法时间复杂度上的差异。

这里主要讲堆优化的 Dijkstra 的实现过程 （因为只会这个）：

  1. 初始化 \(dis(s)=0\)，其他点的 \(dis\) 均为 \(+\infty\)。并且将起点 \(s\) 以及它的距离 \(0\) 入队。

  2. 重复以下操作直至队列（堆）为空：

    1. 取出堆顶元素，并出队。堆是以当前元素的 \(dis\) 尽量小为关键字。

    2. 如果已经访问过这个点 \(u\)（堆顶元素对应的），则无视它进入下一次循环（因为 Dijkstra 算法基于贪心的思想已经更新了经过该点的最短路）。否则标记该点 \(u\) 为已访问。

    3. 遍历以 \(u\) 为起点的边，记终点为 \(v\)，\(w\) 为 \((u, v)\) 的边权，如果满足 \(dis(v) > dis(u) + w\)，则进行松弛操作，并将该元素和其对应的 \(dis\) 入队。

时间复杂度为 \(O(m \log m)\)。

以下为模板题的代码实现：

#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int read(){
	int f=1, k=0; char c = getchar();
	while(c<'0' || c>'9'){if(c=='-') f = -1; c = getchar();}
	while(c>='0' && c<='9'){k = (k<<1) + (k<<3) + (c^48); c = getchar();}
	return f*k;
}

const int MAXN = 100010;
struct node{
	int to, va;
	bool operator <( const node &x )const{
        return x.va < va;
    }
};

vector<node> p[MAXN];
int dis[MAXN]; 
bool vis[MAXN];
int n, m, s;
priority_queue<node> q;

void dijkstra(){
	for(int i=1; i<=n; i++)
		dis[i] = INF;
	dis[s] = 0;
	q.push((node){s, 0});
	while(!q.empty()){
		node x = q.top(); q.pop();
		if(vis[x.to]) continue;
		vis[x.to] = true;
		for(int i=0; i<p[x.to].size(); i++){
			node now = p[x.to][i];
			if(dis[x.to]+now.va < dis[now.to]){
				dis[now.to] = dis[x.to]+now.va;
				q.push((node){now.to, dis[now.to]});
			}
		}
	}
}


int main(){
	n = read(), m = read(), s = read();
	for(int i=1, x, y, z; i<=m; i++){
		x = read(), y = read(), z = read();
		p[x].push_back((node){y, z});
	}
	dijkstra();
	for(int i=1; i<=n; i++){
		printf("%d ", dis[i]);
	}
	return 0;
}

顺带一提最短路计数。多了一个统计。

Bellman–Ford 算法

Bellman–Ford 算法是一种基于松弛操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

实现过程：

不断尝试对图上每一条边进行松弛。每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

每次循环是 \(O(m)\) 的，在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 \(+1\)，而最短路的边数最多为 \(n-1\)，因此整个算法最多执行 \(n-1\) 轮松弛操作。故求其的时间复杂度为 \(O(nm)\)。

还有一种情况，如果从 \(S\) 点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 \(n-1\) 轮，因此如果第 \(n\) 轮循环时仍然存在能松弛的边，说明从 \(S\) 点出发，能够抵达一个负环。

需要注意的是，以 \(S\) 点为源点跑 Bellman–Ford 算法时，如果没有给出存在负环的结果，只能说明从 \(S\) 点出发不能抵达一个负环，而不能说明图上不存在负环。

因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman–Ford 算法。

代码实现（判是否存在负环）：

struct Edge {
  int u, v, w;
};

vector<Edge> edge;

int dis[MAXN], u, v, w;
const int INF = 0x3f3f3f3f;

bool bellmanford(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    bool flag = false;  // 判断一轮循环过程中是否发生松弛操作
    for (int i = 1; i <= n; i++) {
        flag = false;
        for (int j = 0; j < edge.size(); j++) {
            u = edge[j].u, v = edge[j].v, w = edge[j].w;
            if (dis[u] == INF) continue;
            // 无穷大与常数加减仍然为无穷大
            // 因此最短路长度为 INF 的点引出的边不可能发生松弛操作
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                flag = true;
            }
        }
        // 没有可以松弛的边时就停止算法
        if (!flag)
            break;
    }
    // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
    return flag;
}

SPFA 算法

关于 SPFA，它死了。

本质上是经过队列优化过的 Bellman–Ford 算法。所以能做的事情跟它差不多。并且最坏复杂度也是 \(O(nm)\)。

优化思路：

很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。

SPFA 也可以用于判断 \(S\) 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 \(n\) 条边时，说明 \(S\) 点可以抵达一个负环。

实现过程：

  1. 初始化 \(dis(s)=0, vis(s)=1\)，其他点的 \(dis\) 均为 \(+\infty\)，\(vis\) 均为 \(0\)。并且将起点 \(s\) 入队。

  2. 重复以下操作直至队列为空：

    1. 取出队头元素 \(u\)，并出队。并且标记 \(vis(u) = 0\)。

    2. 遍历以 \(u\) 为起点的边，记终点为 \(v\)，\(w\) 为 \((u, v)\) 的边权，如果满足 \(dis(v) > dis(u) + w\)，则进行松弛操作。满足可松弛操作时 \(v\) 不在队列内（\(vis[v] = 0\)）则将 \(v\) 入队，并标记 \(vis[v] = 1\)。

想要判负环的话加个统计，看最短路经过的边数是否 \(\ge n\)。

代码实现（判负环）：

struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;

bool spfa(int n, int s) {
    memset(dis, 63, sizeof(dis));
    dis[s] = 0, vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop(), vis[u] = 0;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
                if (cnt[v] >= n) return false;
                // 在不经过负环的情况下，最短路至多经过 n - 1 条边
                // 因此如果经过了多于 n 条边，一定说明经过了负环
                if (!vis[v]) q.push(v), vis[v] = 1;
            }
        }
    }
    return true;
}

以下为一些关于图的应用...

无向图最小环

暴力解法：

设 \(u\) 和 \(v\) 之间有一条边长为 \(w\) 的边，\(dis(u,v)\) 表示删除 \(u\) 和 \(v\) 之间的连边之后，\(u\) 和 \(v\) 之间的最短路。

那么无向图中的最小环是 \(dis(u,v)+w\)。

注意若是在有向图中求最小环，相对应的公式要修改，最小环是 \(dis(v,u)+w\)。

总时间复杂度 \(O(n^2m)\)。

Floyd:

记原图中 \(u,v\) 之间边的边权为 \(val\left(u,v\right)\)。

我们注意到 Floyd 算法有一个性质：在最外层循环到点 \(k\) 时（尚未开始第 \(k\) 次循环），最短路数组 \(dis\) 中，\(dis_{u,v}\) 表示的是从 \(u\) 到 \(v\) 且仅经过编号在 \(\left[1, k\right)\) 区间中的点的最短路。

由最小环的定义可知其至少有三个顶点，设其中编号最大的顶点为 \(w\)，环上与 \(w\) 相邻两侧的两个点为 \(u,v\)，则在最外层循环枚举到 \(k=w\) 时，该环的长度即为 \(dis_{u,v}+val\left(v,w\right)+val\left(w,u\right)\)。

故在循环时对于每个 \(k\) 枚举满足 \(i<k,j<k\) 的 \((i,j)\)，更新答案即可。

总时间复杂度为 \(O(n^3)\)。

int val[maxn + 1][maxn + 1];  // 原图的邻接矩阵
int dis[maxn + 1][maxn + 1];  // 最短路矩阵

int floyd(int n) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            dis[i][j] = val[i][j];  // 初始化最短路矩阵
    int ans = INT32_MAX;
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i < k; ++i)
            for (int j = 1; j < i; ++j)
                ans = min(ans, dis[i][j] + val[i][k] + val[k][j]);  // 更新答案
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);  // 正常的 floyd 更新最短路矩阵
    }
    return ans;
}

Dijkstra:

枚举所有边，每一次求删除一条边之后对这条边的起点跑一次 Dijkstra，道理同上。

时间复杂度 \(O(m(n+m)\log n)\)。

差分约束

差分约束系统是一种特殊的 \(n\) 元一次不等式组，它包含 \(n\) 个变量 \(x_1,x_2,\dots,x_n\) 以及 \(m\) 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 \(x_i-x_j\leq c_k\)，其中 \(1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m\) 并且 \(c_k\) 是常数。我们要解决的问题是：求一组解 \(x_1=a_1,x_2=a_2,\dots,x_n=a_n\)，使得所有的约束条件得到满足，否则判断出无解。

差分约束系统中的每个约束条件 \(x_i-x_j\leq c_k\) 都可以变形成 \(x_i\leq x_j+c_k\)，这与单源最短路中的三角形不等式 \(d_{v} \leq d_{u}+w_{<u,v>}\) 非常相似。因此，我们可以把每个变量 \(x_i\) 看做图中的一个结点，对于每个约束条件 \(x_i-x_j\leq c_k\)，从结点 \(j\) 向结点 \(i\) 连一条长度为 \(c_k\) 的有向边。

注意到，如果 \(\{a_1,a_2,\dots,a_n\}\) 是该差分约束系统的一组解，那么对于任意的常数 \(d\)，\(\{a_1+d,a_2+d,\dots,a_n+d\}\) 显然也是该差分约束系统的一组解，因为这样做差后 \(d\) 刚好被消掉。

过程:

设 \(dis[0]=0\) 并向每一个点连一条权重为 \(0\) 的边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，\(x_i=dis[i]\) 为该差分约束系统的一组解。

一些转化技巧：

题意 转化 连边
$x_a-x_b \ge c$ $x_b-x_a \leq -c$ $add(a, b, -c);$
$x_a-x_b \leq c$ $x_a-x_b \leq c$ $add(b, a, c);$
$x_a=x_b$ $x_a-x_b\leq0, x_b-x_a\leq0$ $add(b, a, 0), add(a, b, 0);$

最短路树

在单源最短路的过程中，每个点 \(v\) 都存在一些前驱 \(u\)，满足 \(dis(u)+w(u,v)=dis(v)\)，这里 \(w(u,v)\) 是 \(u,v\) 两点之间最短的一条边的边权。

如果我们得到一棵树，根节点为单源最短路的起点 \(s\)，树上每个节点的父亲都是它的某个前驱，则起点到每个点的最短距离，就是这棵树上这个节点到根路径的长度。这样的树就被称作最短路树。

简单来说，定义构建一棵树，使得树上任意不属于根的节点 \(x\)，\(dis(root, x)\) 就是原图起点 \(s\) 到 \(x\) 的最短路。

实现过程：

要得到最短路树，首先需要知道每个点的前驱。
在 Dijkstra 的过程中，我们只需要记录每个点 \(v\) 最后一次被松弛的时候是被哪个点 \(u\) 松弛的，则这个 \(u\) 就是 \(v\) 的前驱。
然后把每个节点的父亲设置成它的前驱就行了。

注意到这样做必定是没有环的。因为将节点出队顺序看作一个拓扑序，节点之间的前驱关系是符合这个拓扑序的。也就是说每个点的前驱必然比它早出队。因此即使图上有零权环也没关系。

P3556 [POI2013] MOR-Tales of seafaring

题意：给 \(n\) 个点 \(m\) 条边无向图，每次询问两个点之间是否有长度为 \(d\) 的路径（不一定是简单路径）。

因为不一定是简单路径，所以可以在一条边上反复横跳，这样只要分别记录 \(u\) 到 \(v\) 的经过奇数条路径的最短路和经过偶数条路径的最短路。查看与 \(k\) 同奇偶的那条路径的最短路是否 \(\le k\)。

如果一个点是孤立的，那么怎么走都无解！

思路一（重要）：分层图。

考虑拆点。将 \((u, v)\) 的路径拆成 \((u, v+n)\) 和 \((u+n, v)\)，这样当当前点为 \(\{ 1, 2, \dots, n \}\) 时，所在层数即为经过偶数条路径能到达的一层，当当前点为 \(\{ n+1, n+2, \dots, n+n \}\) 时，所在层数即为经过奇数条路径能到达的一层。

因为边权均为 \(1\)，所以可以 bfs 统计最短路。

Code 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5005;

vector<int> g[N<<1];
struct node{
    int id, v, w;
};
int dis[N<<1][N<<1];

void bfs(int s){
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        for(int v : g[u]){
            if(!dis[s][v]){ // 防止一条边走过两次之后继续重复
                dis[s][v] = dis[s][u]+1;
                Q.push(v);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, qy; cin>>n>>m>>qy;
    for(int i=1; i<=m; i++){
        int u, v; cin>>u>>v;
        g[u].push_back(v+n); g[v+n].push_back(u);
        g[u+n].push_back(v); g[v].push_back(u+n);
    }
    for(int i=1; i<=n; i++)
        bfs(i);
    for(int i=1; i<=qy; i++){
        int u, v, d; cin>>u>>v>>d;
        if(d & 1){
            if(dis[u][v+n]<=d && dis[u][v+n]) cout<<"TAK\n";
            else cout<<"NIE\n";
        } else{
            if(dis[u][v]<=d && dis[u][v]) cout<<"TAK\n";
            else cout<<"NIE\n";
        }
    }
    return 0;
}

思路二：用不同的数组存距离。

因为 \(k\) 的值非常大，\(n\) 又非常小，为了不 TLE，可以将询问离线，枚举 \(s\) 跑 SPFA，一次性将 \(s\) 有关的询问全解决掉。

Code 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5005;

vector<int> g[N];
struct node{
    int id, v, w;
};
vector<node> query[N];
bool ans[1000005], vis[N];
int dis[N][2]; // 分奇偶

void spfa(int s){
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    dis[s][0] = 0;
    vis[s] = 1; Q.push(s);
    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for(int v : g[u]){
            if(dis[v][1] > dis[u][0]+1){
                dis[v][1] = dis[u][0]+1;
                if(!vis[v]) vis[v] = 1, Q.push(v);
            }
            if(dis[v][0] > dis[u][1]+1){
                dis[v][0] = dis[u][1]+1;
                if(!vis[v]) vis[v] = 1, Q.push(v);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, qy; cin>>n>>m>>qy;
    for(int i=1; i<=m; i++){
        int u, v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1; i<=qy; i++){
        int u, v, d; cin>>u>>v>>d;
        query[u].push_back({i, v, d});
    }
    for(int u=1; u<=n; u++){
        if(!query[u].empty() && g[u].size()){
            spfa(u);
            for(auto p : query[u]){
                if(p.w >= dis[p.v][p.w&1]) ans[p.id] = 1;
            }
        }
    }
    for(int i=1; i<=qy; i++)
        cout<<(ans[i] ? "TAK" : "NIE")<<"\n";
    return 0;
}

百度地图的实时路况

题目大意：给定一张 \(n\) 个点的无向图，点 \(i\) 到点 \(j\) 的距离为 \(G_{i,j}\)，特别地，\(G_{i,j}=-1\) 表示 \(i\) 和 \(j\) 不可达。定义 \(dis(u,v,w)\) 为 \(u\) 出发到 \(v\) 且不经过 \(w\) 的最短路径。（不能到达则为 \(-1\)）求：

\(\sum_{u=1}^n\sum_{v=1}^n\sum_{w=1}^ndis(u,v,w)\)。其中 \(3\leq n\leq300, -1 \leq G_{i,j}\leq10000, G_{i, i}=0\)。

思路：分治 Floyd。

每次递归时计算 \(dis(l, r)\) 表示不使用 \([l,r]\) 中的点条件下的两两之间最短路。向下递归时，将 \(\left[mid+1,r\right]\) 的点加入后递归计算 \(dis(l, mid)\)，同理 \([l,mid]\) 的点加入后递归计算\(dis(mid+1, r)\)。

在\(l=r\)时统计答案即可。

由主定理 \(T(N) = Nn^2+2T(N/2)\) 可以得到时间复杂度为 \(O(n^3\log n)\)。

trick：zzy 称其为时间线段树。撤销 \(\neq\) 删除。有些题目撤销往往比删除好维护非常多。

Code 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 305;

int n, dis[N][N];

ll solve(int l, int r){
    ll ans = 0;
    if(l == r){
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(i!=l && j!=r) ans += dis[i][j];
        return ans;
    }
    int tmp[N][N];
    int mid = l + (r-l)/2;
    memcpy(tmp, dis, sizeof(dis));
    // 左不变右变（右边有不取的元素）
    for(int k=l; k<=mid; k++){
        for(int i=1; i<=n; i++){
            if(i==k) continue;
            for(int j=1; j<=n; j++){
                if(i==j || j==k) continue;
                if(dis[i][k]!=-1 && dis[k][j]!=-1){
                    if(dis[i][j]!=-1) dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
                    else dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
    ans += solve(mid+1, r);
    memcpy(dis, tmp, sizeof(tmp));
    // 右不变同理
    for(int k=mid+1; k<=r; k++){
        for(int i=1; i<=n; i++){
            if(i==k) continue;
            for(int j=1; j<=n; j++){
                if(i==j || j==k) continue;
                if(dis[i][k]!=-1 && dis[k][j]!=-1){
                    if(dis[i][j]!=-1) dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
                    else dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
    ans += solve(l, mid);
    memcpy(dis, tmp, sizeof(tmp));
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>dis[i][j];
    cout<<solve(1, n);
    return 0;
}

P1811 最短路

看到题目是求带限制条件的最短路，想到 BFS。

当走到一个点的时候，记录四个值 \(pos, lst, dis, pre\)，依次代表现在所处的点，走的上一个点，走过的距离，是从队列的几号元素转移来的（便于最后输出方案）。

这样，枚举下一个点 \(v\) 的时候，只用判断如下两个条件：

  1. \(lst, pos, v\) 是否是一个被禁止的三元组。

  2. 把双向边拆成两条单向边后，判断这条边有没有被走过。因为这是 BFS，早标记的时间肯定不大于晚标记的时间。

最终利用 \(pre\) 去递归，输出答案即可。

Code 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define tiii tuple<int, int, int>
#define pii pair<int, int>

int n, m, k, tail, head;
map<tiii, bool> M;
vector<int> g[3005];
map<pii, int> Enum;
int Ecnt;
bool vis[40005];
struct node{
    int pos, lst, dis, pre;
}Q[40005];

void print(int x){
    if(Q[x].pre) print(Q[x].pre);
    cout<<Q[x].pos<<" ";
}

void bfs(){
    head = tail = 1;
    Q[1].pos = 1;
    while(head <= tail){
        node u = Q[head];
        for(auto v : g[u.pos]){
            if(vis[Enum[{u.pos, v}]] || M[{u.lst, u.pos, v}]) continue;
            if(v == n){
                cout<<u.dis+1<<"\n";
                print(head);
                cout<<n;
                exit(0);
            }
            vis[Enum[{u.pos, v}]] = 1;
            Q[++tail] = {v, u.pos, u.dis+1, head};
        }
        head++;
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1; i<=m; i++){
        int u, v; cin>>u>>v;
        g[u].push_back(v);
        Enum[{u, v}] = ++Ecnt;
        g[v].push_back(u);
        Enum[{v, u}] = ++Ecnt;
    }
    for(int i=1; i<=k; i++){
        int a, b, c; cin>>a>>b>>c;
        M[{a, b, c}] = 1;
    }
    bfs();
    cout<<"-1";
    return 0;
}

标签：松弛,int,短路,笔记,学习,vis,push,dis
From： https://www.cnblogs.com/FlyPancake/p/18327533

相关文章

  • (leetcode学习)236. 二叉树的最近公共祖先
    给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）。”示例1：输入：root=[3,5,1,6,2,0,8,nul......
  • 【python学习】retry库用法大全！附示例代码
    Retry是一个用于Python的库，用于在函数调用失败时自动重试。它的目标是简化重试逻辑的编写，处理由于临时性问题（如网络故障、API限制等）导致的失败。Retry的主要特点包括：简单易用：只需使用装饰器或上下文管理器即可实现重试功能。灵活配置：可以配置重试次数、重试间隔、异常......
  • MYSQL-DDL 基础学习
    DDL：数据定义型语言可理解为有关列的操作1、数据库基本操作_DDL#创建数据库db1createdatabasedb1;#使用数据库db1usedb1;#删除数据库db1dropdatabasedb1;#查看所有的数据库showdatabases;#查看当前所使用的数据库selectdatabase();#查看数据库的建库语句sh......
  • ssy中学暑假集训向量学习笔记(应该能完结)
    今天模拟赛T4是个极其恶心的东西，用到了许多高中数学知识，md，引入前置知识。向量定义顾名思义，向量就是有方向的量，在平面直角坐标系上可以用\((a,b)\)表示，图如下：图像上即为由\(A\)指向\(B\)的一条向量。投影投影不好解释，拿图吧。\(AC\)在\(AB\)上的投影就是\(AD\)！！刚学的时候......
  • 初赛笔记
    数学排列组合错排问题：\(D_n=(n-1)(D_{n-1}+D_{n-2})\)\((D_1=0,D_2=1)\)数据结构栈出栈序列数量卡特兰数\(\displaystyleC_i=\frac{C^n_{2n}}{n+1}=\sum_{i=0}^{n}{C_i}{C_{n-i}}\)树一个结点的度为这个节点的子节点数，一棵树的度为所有节点的度数最大值二叉树二叉树......
  • 第四周学习总结
    异常处理异常处理是Java中非常重要的一部分，本周我系统学习了try-catch-finally语句的用法，以及自定义异常和异常链的概念。通过实践，我了解到如何合理地在代码中处理潜在的错误情况，确保程序的健壮性和稳定性。此外，我还学习了如何抛出和捕获特定类型的异常，以及如何使用异常来传递程......
  • Android中Service学习记录
    目录一概述二生命周期2.1启动服务startService()2.2绑定服务bindService()2.3先启动后绑定2.4先绑定后启动三使用3.1本地服务（启动式）3.2可通信的服务（绑定式）3.3前台服务3.4IntentService总结参考一概述Service组件一般用来执行长期在后台的任务，如播放音......
  • MATLAB学习日志DAY20
     结构体(1)结构体是多维MATLAB数组，包含可按文本字段标志符访问的元素。例如，S.name='EdPlum';S.score=83;S.grade='B+'创建一个具有三个字段的标量结构体：S=name:'EdPlum'score:83grade:'B+'与MATLAB环境中的所有其他内容一样，结构体......
  • java学习第四周
    这是学习java的第四周，主要学习了《Java程序设计完全学习手册》第十二章的内容，学习了文件的相关操作，能够实现对文件进行读写等，学习了Java流原理，掌握输入流与输出流、字节流和字符流等，简单认识了对象的序列化等，更熟练地进行数据处理。面向对象程序设计语言有三大特性：封装、继承和多......
  • C++第七次课笔记——引用
    引用作用：给变量取别名语法：数据类型&别名=原名intmain(){ //引用基本语法 inta=10; int&b=a; // cout<<"a="<<a<<endl; cout<<"b="<<b<<endl; b=100; cout<<"a="<<......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99