这就是用来记录我对于《信息学奥赛一本通 · 提高篇》一书中的习题的刷题记录以及学习笔记。
一般分专题来写（全部写一起可能要加载很久...），比如本章就是用来记录最短路的。
再插一句：Loj 真是个不错的 OJ，如果说洛谷是最棒的 OIer 社区，那 Loj 就是最棒的刷题专区。
PS：这里的“最棒的”仅仅指带给我的练习感觉最好，例如画风好康，且仅代表个人意见。
专题介绍：最短路，图论中举足轻重的一块内容，算法众多需要灵活运用，题目变化多样却总离不开核心思想。
如果您不了解 Dijksral,SPFA,Floyd 中的任意一个，可以看看我的文章。
#10072 「一本通 3.2 例 1」Sightseeing Trip
是我太弱了吗？学了这么多年的 Floyd，竟然不知道它有这个功能...。
求无向图的最小环，首选 Floyd。
这里主要来讲一下利用Floyd求解的具体原理
要想用Floyd求解无向图最小环问题，我们首先要深入里了解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]);
但是在这个过程发生了什么呢，为什么可以用来求最小环呢？
首先了解一个道理：
考虑一个图中的最小环 \(u\to v\to k\to u\)，如果我们随意去掉其中一条边 \(u\to v\)，
那么剩下的 \(v\to k\to u\) 一定是图中 \(u\to v\) 间的最短路径。
那么这怎么和 Floyd 算法联系呢？又有一个道理：
在 Floyd 算法枚举 \(k_i\) 的时候，已经得到了前 \(k-1\) 个点的最短路径，
这 \(k-1\) 个点不包括点 \(k\)，并且他们的最短路径中也不包括 \(k\) 点。
那么我们可以从前 \(k-1\) 个点中选出两个点 \(i , j\)，因为 \(i\to j\) 已经是 $ i , j $ 间的最短路径，且这个路径不包含 \(k\) 点。
所以连接 \(i\to j\to k\to i\)，我们就得到了一个经过 \(i , j , k\) 的最小环
最后每次更新 \(ans\) 的最小值即可。
本题讲解转载自这篇博客。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cmath>
#include <vector>
#define N 310
#define maxd 0x3f3f3f3f
using namespace std;
int n, m, a[N][N], d[N][N], pre[N][N];
long long ans = maxd;
vector<int> path;
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < ‘0‘ || c > ‘9‘) f = (c == ‘-‘) ? -1 : 1, c = getchar();
while (c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48, c = getchar();
return x * f;
}
void get_path(int x, int y) {
if (!pre[x][y])
return;
get_path(x, pre[x][y]);
path.push_back(pre[x][y]);
get_path(pre[x][y], y);
return;
}
int main() {
n = read();
m = read();
int x, y, z;
memset(a, 0x3f, sizeof(a));
for (int i = 1; i <= n; i++) a[i][i] = 0;
for (int i = 1; i <= m; i++) {
x = read();
y = read();
z = read();
a[x][y] = a[y][x] = min(a[x][y], z);
}
memcpy(d, a, sizeof(a));
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++)
for (int j = i + 1; j < k; j++)
if ((long long)d[i][j] + a[j][k] + a[k][i] < ans) {
ans = d[i][j] + a[j][k] + a[k][i];
path.clear();
path.push_back(i);
get_path(i, j);
path.push_back(j);
path.push_back(k);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
pre[i][j] = k;
}
}
if (ans == maxd) {
printf("No solution.\n");
return 0;
}
for (int i = 0; i < path.size(); i++) printf("%d ", path[i]);
return 0;
}
这道题我是用 BFS + 状压 过的，因为这个方法比最短路省空间，下面给出的也是我的方法的代码。
但是这并不会影响在这里讲解分层图最短路的思路。
比较直接的思想就是将图分为 \(2^k\) 层（\(k\) 为钥匙的种数），每一层的表示拥有钥匙的状态。（不就是状压）
然后就到处乱搞连边，得到一个极其复杂的图形，在上面跑最短路即可。
注意：答案为 \(max_{1\leq i\leq 2^k}\{dis[i][n]\}\)。下面是 BFS + 状压的代码。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
#include <queue>
#define N 15
using namespace std;
int n, m, p, k, s;
int door[N][N][N][N], key[N][N][N], dis[N][N][1 << 14], cnt[N][N];
bool vis[N][N][1 << 14];
struct node {
int x, y, val;
};
int dx[5] = { 0, 0, 0, 1, -1 };
int dy[5] = { 0, 1, -1, 0, 0 };
queue<node> q;
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < ‘0‘ || c > ‘9‘) f = (c == ‘-‘) ? -1 : 1, c = getchar();
while (c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48, c = getchar();
return x * f;
}
bool chck(int x, int y, int fx, int fy, int val, int nxt) {
if (fx < 1 || fx > n || fy < 1 || fy > m)
return false;
int d = door[x][y][fx][fy];
if (d == -1)
return false;
if (d && !(val & (1 << d)))
return false;
if (vis[fx][fy][nxt])
return false;
return true;
}
int bfs() {
memset(vis, false, sizeof(vis));
int first = 0;
for (int i = 1; i <= cnt[1][1]; i++) first |= (1 << key[1][1][i]);
q.push((node){ 1, 1, first });
while (!q.empty()) {
int x = q.front().x;
int y = q.front().y;
int val = q.front().val;
q.pop();
if (x == n && y == m)
return dis[x][y][val];
for (int i = 1; i <= 4; i++) {
int fx = dx[i] + x;
int fy = dy[i] + y;
int nxt = val;
for (int i = 1; i <= cnt[fx][fy]; i++) nxt |= (1 << key[fx][fy][i]);
if (!chck(x, y, fx, fy, val, nxt))
continue;
vis[fx][fy][nxt] = true;
dis[fx][fy][nxt] = dis[x][y][val] + 1;
q.push((node){ fx, fy, nxt });
}
}
return -1;
}
int main() {
n = read();
m = read();
p = read();
k = read();
int type, x, y, xx, yy;
for (int i = 1; i <= k; i++) {
x = read();
y = read();
xx = read();
yy = read();
type = read();
if (type)
door[x][y][xx][yy] = door[xx][yy][x][y] = type;
else
door[x][y][xx][yy] = door[xx][yy][x][y] = -1;
}
s = read();
for (int i = 1; i <= s; i++) {
x = read();
y = read();
type = read();
key[x][y][++cnt[x][y]] = type;
}
printf("%d\n", bfs());
return 0;
}
具体看这篇文章。
之前考试考了原题...，然后我没注意到是单向边，就直接输出了 \(max\{dis[i]\times 2\}\)，然后爆 0 滚粗...。
然后考完后想了一个很暴力的方法：
就是以每一号节点为根节点跑单源最短路，然后答案就是 \(max\{dis[1,i]+dis[i,1]\}\)。
好像跑得还挺快
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#define N 1010
#define M 100010
using namespace std;
int n, m, v, dis[N], diss[N], head[N], cnt = 0;
bool vis[N];
struct Edge {
int nxt, to, val;
} edge[M];
priority_queue<pair<int, int> > q;
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < ‘0‘ || c > ‘9‘) f = (c == ‘-‘) ? -1 : 1, c = getchar();
while (c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48, c = getchar();
return x * f;
}
void addedge(int x, int y, int z) {
cnt++;
edge[cnt].nxt = head[x];
edge[cnt].to = y;
edge[cnt].val = z;
head[x] = cnt;
return;
}
void dij(int s) {
memset(vis, false, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
q.push(make_pair(0, s));
while (!q.empty()) {
int now = q.top().second;
q.pop();
if (vis[now])
continue;
vis[now] = true;
for (int i = head[now]; i; i = edge[i].nxt) {
int y = edge[i].to, z = edge[i].val;
if (dis[y] > dis[now] + z) {
dis[y] = dis[now] + z;
q.push(make_pair(-dis[y], y));
}
}
}
return;
}
int main() {
n = read(), m = read(), v = read();
int x, y, z;
for (int i = 1; i <= m; i++) {
x = read(), y = read(), z = read();
addedge(x, y, z);
}
dij(v);
memcpy(diss, dis, sizeof(dis));
int ans = 0;
for (int i = 1; i <= n; i++) {
dij(i);
ans = max(ans, dis[v] + diss[i]);
}
printf("%d\n", ans);
return 0;
}
当然这不是正解。（废话）
一句话：正反建边跑两次最短路就可以了。（这里用简单的 SPFA 实现）
#include <bits/stdc++.h>
using namespace std;
int n, m, k, ans;
int ecnt = 0, tcnt = 0;
int zhead[1000 + 5], fhead[1000 + 5];
int zdis[1000 + 5], fdis[1000 + 5];
bool vst[1000 + 5];
struct edge {
int from, to, len;
int nxt;
} g[100000 + 5], f[100000 + 5];
inline int read() {
int x = 0;
char ch = getchar();
while (ch < 48 || ch > 57) ch = getchar();
while (ch <= 57 && ch >= 48) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x;
}
inline void addedge1(int u, int v, int w) {
ecnt++;
g[ecnt].from = u;
g[ecnt].to = v;
g[ecnt].len = w;
g[ecnt].nxt = zhead[u];
zhead[u] = ecnt;
}
inline void addedge2(int u, int v, int w) {
tcnt++;
f[ecnt].from = u;
f[ecnt].to = v;
f[ecnt].len = w;
f[ecnt].nxt = fhead[u];
fhead[u] = tcnt;
}
inline void SPFA1(int S) {
memset(fdis, 0x3f, sizeof(fdis));
memset(vst, 0, sizeof(vst));
vst[S] = 1;
queue<int> q;
fdis[S] = 0;
q.push(S);
while (!q.empty()) {
int u = q.front();
q.pop();
vst[u] = 0;
for (register int i = fhead[u]; i; i = f[i].nxt) {
int v = f[i].to;
if (fdis[v] > fdis[u] + f[i].len) {
fdis[v] = fdis[u] + f[i].len;
if (!vst[v]) {
vst[v] = 1;
q.push(v);
}
}
}
}
}
inline void SPFA2(int S) {
memset(zdis, 0x3f, sizeof(zdis));
memset(vst, 0, sizeof(vst));
vst[S] = 1;
queue<int> q;
zdis[S] = 0;
q.push(S);
while (!q.empty()) {
int u = q.front();
q.pop();
vst[u] = 0;
for (register int i = zhead[u]; i; i = g[i].nxt) {
int v = g[i].to;
if (zdis[v] > zdis[u] + g[i].len) {
zdis[v] = zdis[u] + g[i].len;
if (!vst[v]) {
vst[v] = 1;
q.push(v);
}
}
}
}
}
int main() {
n = read(), m = read(), k = read();
for (register int i = 1, x, y, z; i <= m; i++) {
x = read(), y = read(), z = read();
addedge1(x, y, z);
addedge2(y, x, z);
}
SPFA1(k);
SPFA2(k);
for (register int i = 1; i <= n; i++) ans = max(ans, zdis[i] + fdis[i]);
printf("%d\n", ans);
system("pause");
return 0;
}
#10076 「一本通 3.2 练习 2」Roadblocks
求严格次短路有三种方法：
以下内容转载自这篇文章。
dijkstra:
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cmath>
#include <queue>
#define N 5010
#define M 100010
using namespace std;
int n, m, dis[N], diss[N], head[N], cnt = 0;
struct Edge {
int nxt, to, val;
} ed[M << 1];
priority_queue<pair<int, int> > q;
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < ‘0‘ || c > ‘9‘) f = (c == ‘-‘) ? -1 : 1, c = getchar();
while (c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48, c = getchar();
return x * f;
}
void addedge(int x, int y, int z) {
++cnt;
ed[cnt].nxt = head[x];
ed[cnt].to = y;
ed[cnt].val = z;
head[x] = cnt;
return;
}
void dij() {
memset(dis, 0x3f, sizeof(dis));
memset(diss, 0x3f, sizeof(diss));
dis[1] = 0;
q.push(make_pair(0, 1));
while (!q.empty()) {
int d = -q.top().first, now = q.top().second;
q.pop();
if (d > diss[now])
continue;
for (int i = head[now]; i; i = ed[i].nxt) {
int y = ed[i].to, z = ed[i].val;
int d2 = d + z;
if (dis[y] > d2) {
swap(dis[y], d2);
q.push(make_pair(-dis[y], y));
}
if (diss[y] > d2 && dis[y] < d2) {
diss[y] = d2;
q.push(make_pair(-diss[y], y));
}
}
}
return;
}
int main() {
n = read(), m = read();
int x, y, z;
for (int i = 1; i <= m; i++) {
x = read(), y = read(), z = read();
addedge(x, y, z);
addedge(y, x, z);
}
dij();
printf("%d\n", diss[n]);
return 0;
}
dijkstra+A*:
首先用 dijkstra 处理出从n到每个点的最短距离，然后调用A*算法。
从1开始处理，每次把相邻的点的边权加上，再存进队列，这样每次存进去的就是1到每个点的距离。
然后根据这个距离+当前点到n的最短距离排序。
那么第一次n点取出来时就是1到n的最短路，然后继续加相邻边权放入队列。
那么第二次处理到n，就是最短路加上一条除了最短路经过的边以外的一条最短边的值，也就是次短距离了。
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=5000+10;
int n,m,u,v,val;
int dis[maxn];
struct P
{
int to,cost;
bool operator < (const P & a) const
{
return cost>a.cost;
}
};
vector<P> edge[maxn];
void Dijkstra()
{
fill(dis,dis+n+2,INF);
dis[n]=0;
priority_queue<P> qu;
qu.push(P{n,0});
while(!qu.empty())
{
P x=qu.top();
qu.pop();
for(int i=0;i<edge[x.to].size();i++)
{
P y=edge[x.to][i];
if(dis[y.to]>dis[x.to]+y.cost)
{
dis[y.to]=dis[x.to]+y.cost;
qu.push(P{y.to,dis[y.to]});
}
}
}
}
struct node
{
int to,len;
bool operator < (const node & a) const
{
return len+dis[to]>a.len+dis[a.to];
}
};
int A_star()
{//if(dis[1]==INF) return -1;当不存在最短路时要加上，不然会死循环。
priority_queue<node> qu;
qu.push(node{1,0});
int num=0;
while(!qu.empty())//这个地方有点搜索的味道，从1开始不断加上相邻的点的边权，然后放入队列。就是从1开始不断向n拓展
{
node a=qu.top();
qu.pop();
if(a.to==n) num++;
if(num==2) return a.len;
for(int i=0;i<edge[a.to].size();i++)
{
P b=edge[a.to][i];
qu.push(node{b.to,a.len+b.cost});//到b.to这个点，然后1到b.to的距离就是a.to的距离加上ab间边的权值。
}
}
return -1;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<=n;i++)
edge[i].clear();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&val);
edge[u].push_back(P{v,val});
edge[v].push_back(P{u,val});
}
Dijkstra();
printf("%d\n",A_star());
}
return 0;
}
两次最短：
从起点跑一次最短路，然后再从终点跑一次最短路，然后遍历一遍所有的边。
次短路的距离就是其中某条边的权值加上起点到一个点的最短路加上终点到另一个点的最短路
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#pragma GCC optimize(2)
#define INF 0x3f3f3f3f
using namespace std;
const int N=5000+5;
int n,m,u,v,val;
struct P
{
int to,cost;
};
vector<vector<P> > G;//刚学的二维vector使用，使用前需要resize其大小
int dis1[N],dis2[N],vis[N];
void spfa(int s,int *dis)
{
memset(vis,0,sizeof(vis));
dis[s]=0;
queue<int> qu;
qu.push(s);
while(!qu.empty()){
int U=qu.front();
qu.pop();
vis[U]=0;
for(int i=0;i<G[U].size();i++){
P V=G[U][i];
if(dis[V.to]>dis[U]+V.cost){
dis[V.to]=dis[U]+V.cost;
if(!vis[V.to]){
vis[V.to]=1;
qu.push(V.to);
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
G.resize(n+1); G.clear();
memset(dis1,INF,sizeof(dis1));
memset(dis2,INF,sizeof(dis2));
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&val);
G[u].push_back(P{v,val});
G[v].push_back(P{u,val});
}
spfa(1,dis1);
spfa(n,dis2);
int ans=INF;
for(int i=1;i<=n;i++){//遍历所有的边
for(int j=0;j<G[i].size();j++){
P now=G[i][j];
int temp=dis1[i]+dis2[now.to]+now.cost;
if(temp>dis1[n] && temp<ans) ans=temp;//严格最小
}
}
printf("%d\n",ans);
}
return 0;
}
都无权无向图了，直接就记录答案不久好了吗，这么简单。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#define MOD 100003
#define N 1000010
using namespace std;
int n, m, dep[N], ans[N];
bool vis[N];
vector<int> v[N];
queue<int> q;
int main() {
scanf("%d %d", &n, &m);
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
memset(vis, false, sizeof(vis));
q.push(1);
vis[1] = true;
ans[1] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i < v[now].size(); i++) {
int to = v[now][i];
if (!vis[to]) {
vis[to] = true;
dep[to] = dep[now] + 1;
q.push(to);
}
if (dep[to] == dep[now] + 1)
ans[to] = (ans[to] + ans[now]) % MOD;
}
}
for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
// system("pause");
return 0;
}
分别从源点以及a,b,c,d,e五个节点跑最短路，记录下来后 DFS 暴力枚举方案数。（总共才 \(2^5\) 个）
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#define N 50010
#define M 100010
using namespace std;
int n, m, v, dis[10][N], head[N], cnt = 0, a[10], ans = 999999999;
bool vis[N];
struct Edge {
int nxt, to, val;
} edge[M << 1];
priority_queue<pair<int, int> > q;
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < ‘0‘ || c > ‘9‘) f = (c == ‘-‘) ? -1 : 1, c = getchar();
while (c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48, c = getchar();
return x * f;
}
void addedge(int x, int y, int z) {
cnt++;
edge[cnt].nxt = head[x];
edge[cnt].to = y;
edge[cnt].val = z;
head[x] = cnt;
return;
}
void dij(int x, int s) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) dis[x][i] = 0x3f3f3f3f;
dis[x][s] = 0;
q.push(make_pair(0, s));
while (!q.empty()) {
int now = q.top().second;
q.pop();
if (vis[now])
continue;
vis[now] = true;
for (int i = head[now]; i; i = edge[i].nxt) {
int y = edge[i].to, z = edge[i].val;
if (dis[x][y] > dis[x][now] + z) {
dis[x][y] = dis[x][now] + z;
q.push(make_pair(-dis[x][y], y));
}
}
}
return;
}
int path[10], use[N];
void work() {
int sum = dis[0][a[path[1]]];
for (int i = 2; i <= 5; i++) sum += dis[path[i - 1]][a[path[i]]];
ans = min(ans, sum);
return;
}
void dfs(int x) {
if (x == 6) {
work();
return;
}
for (int i = 1; i <= 5; i++) {
if (use[i])
continue;
use[i] = true;
path[x] = i;
dfs(x + 1);
use[i] = false;
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= 5; i++) a[i] = read();
int x, y, z;
for (int i = 1; i <= m; i++) {
x = read(), y = read(), z = read();
addedge(x, y, z);
addedge(y, x, z);
}
dij(0, 1);
for (int i = 1; i <= 5; i++) dij(i, a[i]);
memset(use, false, sizeof(use));
dfs(1);
printf("%d\n", ans);
return 0;
}
好经典的分层图最短路。
建立三层图：
然后发现有负权，所以跑一遍 SPFA 即可。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
#define maxn 100010
#define maxm 500010
#define maxd 999999999
using namespace std;
int n, m, a[maxn], dis[maxn * 3 + 1];
bool use[maxn * 3 + 1];
queue<int> q;
struct node {
int to, val;
};
vector<node> v[maxn * 3 + 1];
void addedge(int x, int y) {
v[x].push_back((node){ y, 0 });
v[x + n].push_back((node){ y + n, 0 });
v[x + 2 * n].push_back((node){ y + 2 * n, 0 });
v[x].push_back((node){ y + n, -a[x] });
v[x + n].push_back((node){ y + 2 * n, a[x] });
return; //核心代码
}
void spfa() {
for (int i = 1; i <= n; i++) dis[i] = -maxd;
memset(use, false, sizeof(use));
q.push(1);
use[1] = true;
dis[1] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
use[now] = false;
for (int i = 0; i < v[now].size(); i++) {
int y = v[now][i].to;
int z = v[now][i].val;
if (dis[y] < dis[now] + z) {
dis[y] = dis[now] + z;
if (!use[y]) {
q.push(y);
use[y] = true;
}
}
}
}
return;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int x, y, z;
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &x, &y, &z);
addedge(x, y);
if (z == 2)
addedge(y, x);
}
v[n].push_back((node){ n * 3 + 1, 0 });
v[n * 3].push_back((node){ n * 3 + 1, 0 });
n = 3 * n + 1;
spfa();
printf("%d\n", dis[n]);
// system("pause");
return 0;
}
同样是经典的分层图最短路问题。
思路就是将图分为 \(k+1\) 层，每层之间的节点边权为 \(1\)，第 \(i\) 层表示还可以跑 \(k-i+1\) 步。
如果某个点有加油站，那么高层至基层的边权为 \(A_i\)，否则为 \(A_i+C_i\)。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#define N 500010
#define M 5000100
#define maxd 999999999
using namespace std;
int n, k, a, b, c;
int dis[N], oil;
bool use[N];
int head[N], cnt = 0;
struct node {
int next, to, val;
} edge[M];
priority_queue<pair<int, int> > q;
void addedge(int x, int y, int z, int xx, int yy, int zz, int w) {
int p1 = (z - 1) * n * n + (x - 1) * n + y;
int p2 = (zz - 1) * n * n + (xx - 1) * n + yy;
cnt++;
edge[cnt].next = head[p1];
edge[cnt].to = p2;
edge[cnt].val = w;
head[p1] = cnt;
return;
}
void build() {
scanf("%d %d %d %d %d", &n, &k, &a, &b, &c);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &oil);
for (int l = 1; l <= k; l++) {
addedge(i, j, l, i, j, l + 1, 0);
}
if (oil) {
for (int l = 2; l <= k + 1; l++) {
addedge(i, j, l, i, j, 1, a);
}
if (i < n)
addedge(i, j, 1, i + 1, j, 2, 0);
if (j < n)
addedge(i, j, 1, i, j + 1, 2, 0);
if (i > 1)
addedge(i, j, 1, i - 1, j, 2, b);
if (j > 1)
addedge(i, j, 1, i, j - 1, 2, b);
} else {
for (int l = 2; l <= k + 1; l++) {
addedge(i, j, l, i, j, 1, a + c);
}
for (int l = 1; l <= k; l++) {
if (i < n)
addedge(i, j, l, i + 1, j, l + 1, 0);
if (j < n)
addedge(i, j, l, i, j + 1, l + 1, 0);
if (i > 1)
addedge(i, j, l, i - 1, j, l + 1, b);
if (j > 1)
addedge(i, j, l, i, j - 1, l + 1, b);
}
}
}
}
return;
} //分层图最短路的存图都好恶心啊。
void dij() {
memset(dis, 0x3f, sizeof(dis));
memset(use, false, sizeof(use));
dis[1] = 0;
q.push(make_pair(0, 1));
while (!q.empty()) {
int now = q.top().second;
q.pop();
if (use[now])
continue;
use[now] = true;
for (int i = head[now]; i; i = edge[i].next) {
int y = edge[i].to;
int z = edge[i].val;
if (dis[y] > dis[now] + z) {
dis[y] = dis[now] + z;
q.push(make_pair(-dis[y], y));
}
}
}
return;
}
int main() {
build();
dij();
int ans = maxd;
for (int i = 1; i <= k + 1; i++) {
ans = min(ans, dis[n * n * i]);
}
printf("%d\n", ans);
// system("pause");
return 0;
}
简化题意：
给定一张图，有的边是无向边，有的是有向边，有向边不会出现在环中，且有可能是负权值。
现在给定起点s，求出s到其余所有点的最短路长度。
任何存在负权边的图都不可以用 dijksral 并且数据经过特殊构造卡 spfa。
所以要引出一种神仙做法，利用本题的无向边无负权，且单向边不会出现在环中，先再每个联通块内求dij。
然后用拓扑排序处理联通块之间的距离 先将所有无向边加入图。
然后求出所有联通块，将联通块缩点 然后再加入有向边，按拓扑排序进行。
算法流程：
你可能会有疑惑，因为这里并没有处理联通两个连通块的负权边。
其实我们已经处理了（一脸懵逼.jpg），具体看注释。
然后就可以切题了。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cmath>
#include <queue>
#define INF 0x3f3f3f3f
#define N 25010
#define M 150010
using namespace std;
int n, m1, m2, s;
int ru[N], dis[N], col[N], head[N], cnt = 0, totc = 0;
bool vis[N];
struct Edge {
int nxt, to, val;
} ed[M];
priority_queue<pair<int, int> > q;
queue<int> qq;
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < ‘0‘ || c > ‘9‘) f = (c == ‘-‘) ? -1 : 1, c = getchar();
while (c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48, c = getchar();
return x * f;
}
void addedge(int x, int y, int z) {
cnt++;
ed[cnt].nxt = head[x];
ed[cnt].to = y;
ed[cnt].val = z;
head[x] = cnt;
return;
}
void dfs(int x) {
for (int i = head[x]; i; i = ed[i].nxt) {
int y = ed[i].to;
if (!col[y]) {
col[y] = totc;
dfs(y);
}
}
return;
}
void dij() {
while (!q.empty()) {
int now = q.top().second;
q.pop();
if (vis[now])
continue;
vis[now] = true;
for (int i = head[now]; i; i = ed[i].nxt) {
int y = ed[i].to, z = ed[i].val;
if (dis[y] > dis[now] + z) {
dis[y] = dis[now] + z;
//这里是先松弛，在判断是否在一个连通块。
//也就是说，当遇到连接两个连通块的负权边时，会同样进行松弛但不会入队。
//虽然 Dijkscal 不能处理负权边，但是如果不进队仅仅是松弛操作，它还是可以胜任的。
//这里就巧妙的讲负权边也包括在内了。
if (col[now] == col[y])
q.push(make_pair(-dis[y], y));
}
if (col[now] != col[y] && !--ru[col[y]])
qq.push(col[y]);
}
}
return;
}
int main() {
n = read();
m1 = read();
m2 = read();
s = read();
int x, y, z;
for (int i = 1; i <= m1; i++) {
x = read();
y = read();
z = read();
addedge(x, y, z);
addedge(y, x, z);
}
for (int i = 1; i <= n; i++) {
if (!col[i]) {
col[i] = ++totc;
dfs(i);
}
}
for (int i = 1; i <= m2; i++) {
x = read();
y = read();
z = read();
addedge(x, y, z);
++ru[col[y]];
}
qq.push(col[s]);
for (int i = 1; i <= totc; i++)
if (!ru[i])
qq.push(i);
memset(dis, 127, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[s] = 0;
while (!qq.empty()) {
int i = qq.front();
qq.pop();
for (int j = 1; j <= n; j++)
if (col[j] == i)
q.push(make_pair(-dis[j], j));
dij();
}
for (int i = 1; i <= n; i++) {
if (dis[i] > INF)
printf("NO PATH\n");
else
printf("%d\n", dis[i]);
}
return 0;
}
原文：https://www.cnblogs.com/lpf-666/p/12683161.html