次短路

模型建立

一般题目中会明确告诉你要求第二短路或者次短路

思路

主要思路一共有两种，一种为记录路径然后删边，另一种是开一个dis2记录次短路.

暴力删边

直接上代码吧..

#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define M 210

using namespace std;
int n, m, add_edge; bool bian[M][M];
double px[M], py[M], dis[M]; 
int head[M * M * 2], from[M], vis[M];
struct CCC {
	int next, to; double dis;
}edge[M * M * 2];
struct node {
	int x; double dis;
	bool operator < (const node &b) const {
		return dis > b.dis;
	}
};

int read() {
	int s = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

double distant(double x, double y, double a, double b) {
	return sqrt((x - a) * (x - a) + (y - b) * (y - b));
}

void add(int from, int to, double dis) {
	edge[++add_edge].next = head[from];
	edge[add_edge].to = to;
	edge[add_edge].dis = dis;
	head[from] = add_edge;
}

void dijkstra(int sy) {
	for (int i = 1; i <= n; i++) dis[i] = 444444444444.00;
	memset(vis, 0, sizeof vis);
	priority_queue<node> q;
	q.push((node){1, 0}), dis[1] = 0;
	while (!q.empty()) {
		node fr = q.top(); q.pop();
		int x = fr.x;
		if (vis[x]) continue;
		vis[x] = 1;
		for (int i = head[x]; i; i = edge[i].next) {
			int to = edge[i].to;
			if (bian[x][to] || bian[to][x]) continue;
			if (!vis[to] && dis[to] > dis[x] + edge[i].dis) {
				dis[to] = dis[x] + edge[i].dis; 
				if (sy) from[to] = x;
				q.push((node){to, dis[to]}); 
			}
		}
	} 
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++)
		px[i] = read(), py[i] = read();
	for (int i = 1, x, y; i <= m; i++) {
		x = read(), y = read();
		double d = distant(px[x], py[x], px[y], py[y]);
		add(x, y, d), add(y, x, d);
	}
	dijkstra(1);
	double an = dis[n];
	int sy = n; double ans = 444444444444.00;
	while (sy != 1) {
		bian[from[sy]][sy] = 1, bian[sy][from[sy]] = 1;
		dijkstra(0);
		if (dis[n] > an)
			ans = min(ans, dis[n]);
		bian[from[sy]][sy] = 0, bian[sy][from[sy]] = 0;
		sy = from[sy];
	}
	if (ans == 444444444444.00) puts("-1");
	else printf("%.2lf
", ans);
}

the other

以洛谷P2865 [USACO06NOV]Roadblocks G为例
这个题以为有重边，然后暴力删边操作之后只有90分就很难受.

在用(dijkstra)时候，就直接更新次短路，用(dis[])代表最短路，用(dis2[])代表次短路，
然后在松弛的时候同时更新两个数组，要判断三个条件
（(u)是当前考虑的点，(v)是与(u)有边相连的点，(d(u,v))表示从(u)到(v)的边长）

(1.)如果(dis[v]>dis[u]+d(u,v))，则更新(dis[v])
(2.)如果(dis[v]<dis[u]+d(u,v))（不能取等，否则(dis2[v])和(dis[v])可能相等）
且(dis2[v]>dis[u]+d(u,v))，则更新(dis2[v])
(3.)如果(dis2[v]>dis2[u]+d(u,v))，则更新(dis2[v])（显然，如果2成立，
更新后(dis2[v]=dis[u]+d(u,v)<dis2[u]+d(u,v))，即(3)一定不成立）

如果上述三个条件中有任意一个成立，则将v入队。

code

#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define M 5010

using namespace std;
int n, m;
int head[N << 1], add_edge, nx, ny, ndis;
int dis[M], dis2[M], vis[M], from[M], bian[M][M];
struct CCC {
	int next, to, dis;
}edge[N << 1];
struct node {
	int x, dis;
	bool operator < (const node &b) const {
		return dis > b.dis;
	}
};

int read() {
	int s = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void add(int from, int to, int dis) {
	edge[++add_edge].next = head[from];
	edge[add_edge].to = to;
	edge[add_edge].dis = dis;
	head[from] = add_edge;
}

void dijkstra(int sy) {
	memset(dis, 0x3f, sizeof dis);
	memset(dis2, 0x3f, sizeof dis2);
	priority_queue<node> q;
	q.push((node){1, 0}); dis[1] = 0;
	while (!q.empty()) {
		node fr = q.top(); q.pop();
		int x = fr.x;
		for (int i = head[x]; i; i = edge[i].next) {
			int to = edge[i].to;
			if (dis[to] >= dis[x] + edge[i].dis) {
				dis[to] = dis[x] + edge[i].dis;
				q.push((node){to, dis[to]});
			} else if (dis2[to] > dis[x] + edge[i].dis) {
				dis2[to] = dis[x] + edge[i].dis;
				q.push((node){to, dis[to]});
			}
			if (dis2[to] > dis2[x] + edge[i].dis)
				dis2[to] = dis2[x] + edge[i].dis;
		}
	}
}

int main() {
	n = read(), m = read();
	for (int i = 1, x, y, d; i <= m; i++) {
		x = read(), y = read(), d = read();
		add(x, y, d), add(y, x, d);
		if (!bian[x][y]) bian[x][y] = d, bian[y][x] = d;
		else bian[x][y] = min(bian[x][y], d), bian[y][x] = bian[x][y];
	}
	dijkstra(1);
	cout << dis2[n] << "
";
}