19.4万

StarLi9ht

bre
_coding

cjh20090318
shuaige

taoxy

stamina_zeng
yxc的小迷妹
Royal
18910310021

AC天

holy_crap

“进阶”

$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

Bellman-Ford 算法：

1. 循环 $n$ 次。
2. 每层循环循环每条边，使用三角不等式进行松弛操作。
3. 可以处理负权边，判断负环。

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n, m, k;
int dist[N], back[N];
struct Edge {
int a, b, c;
} edge[M];

int bellman_ford() {
dist[1] = 0;
for (int i = 1; i <= k; i++) {
memcpy(back, dist, sizeof dist);
for (int j = 1; j <= m; j++) {
int a = edge[j].a, b = edge[j].b, w = edge[j].c;
dist[b] = min(dist[b], back[a] + w);
}
}
if (dist[n] >= 0x3f3f3f3f / 2) return -0x3f3f3f3f;
return dist[n];
}

int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
edge[i] = {u, v, w};
}
memset(dist, 0x3f3f3f3f, sizeof dist);
int ans = bellman_ford();
if (ans == -0x3f3f3f3f) puts("impossible");
else printf("%d", ans);
return 0;
}


$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

Bellman-Ford 算法：

1. 循环 $n$ 次。
2. 每层循环循环每条边，使用三角不等式进行松弛操作。
3. 可以处理负权边，判断负环。

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n, m, k;
int dist[N], back[N];
struct Edge {
int a, b, c;
} edge[M];

int bellman_ford() {
dist[1] = 0;
for (int i = 1; i <= k; i++) {
memcpy(back, dist, sizeof dist);
for (int j = 1; j <= m; j++) {
int a = edge[j].a, b = edge[j].b, w = edge[j].c;
dist[b] = min(dist[b], back[a] + w);
}
}
if (dist[n] >= 0x3f3f3f3f / 2) return -0x3f3f3f3f;
return dist[n];
}

int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
edge[i] = {u, v, w};
}
memset(dist, 0x3f3f3f3f, sizeof dist);
int ans = bellman_ford();
if (ans == -0x3f3f3f3f) puts("impossible");
else printf("%d", ans);
return 0;
}


$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

AcWing 849. Dijkstra求最短路 I进行堆优化。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
memset(d, 0x3f3f3f3f, sizeof d);
memset(st, 0, sizeof st);
d[1] = 0;
q.push({0, 1});
while (q.size()) {
int x = q.top().second;
q.pop();
if (st[x]) continue;
st[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i], z = edge[i];
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
q.push({-d[y], y});
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i =1 ; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
}
dijkstra();
if (d[n] != 0x3f3f3f3f) cout<<d[n];
else puts("-1");
}


$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

AcWing 849. Dijkstra求最短路 I进行堆优化。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
memset(d, 0x3f3f3f3f, sizeof d);
memset(st, 0, sizeof st);
d[1] = 0;
q.push({0, 1});
while (q.size()) {
int x = q.top().second;
q.pop();
if (st[x]) continue;
st[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i], z = edge[i];
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
q.push({-d[y], y});
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i =1 ; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);