（次短路）已知有一个n 个点m 条边的有向图G，并且给定图中的两个点s 和t，求次

短路（长度严格大于最短路的最短路径）。如果不存在，输出一行“-1”。如果存在，输出两

行，第一行表示此段路经的长度，第二行表示此段路的一个方案

#include <cstdio>


#include <queue>


#include <utility>


#include <cstring>


using namespace std;


const int maxn = 2e5 + 10, maxm = 1e6 + 10, inf = 522133279;


int n, m, s, t;


int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;


int dis[maxn << 1], *dis2;


int pre[maxn << 1], *pre2;


bool vis[maxn << 1];


void add(int a, int b, int c) {


	++tot;


	nxt[tot] = head[a];


	to[tot] = b;


	w[tot] = c;


	head[a] = tot;


}


bool upd(int a, int b, int d, priority_queue<pair<int, int> > &q) {


	if (d >= dis[b])return false;


	if (b < n) __(1)__ ;


	q.push( __(2)__ );


	dis[b] = d;


	pre[b] = a;


	return true;


}


void solve() {


	priority_queue<pair<int, int> >q;


	q.push(make_pair(0, s));


	memset(dis, __(3)__ , sizeof(dis));


	memset(pre, -1, sizeof(pre));


	dis2 = dis + n;


	pre2 = pre + n;


	dis[s] = 0;


	while (!q.empty()) {


		int aa = q.top().second;


		q.pop();


		if (vis[aa])continue;


		vis[aa] = true;


		int a = aa % n;


		for (int e = head[a]; e; e = nxt[e]) {


			int b = to[e], c = w[e];


			if (aa < n) {


				if (!upd(a, b, dis[a] + c, q))


					__(4)__


				} else {


				upd(n + a, n + b, dis2[a] + c, q);


			}


		}


	}


}


void out(int a) {


	if (a != s) {


		if (a < n)


			out(pre[a]);


		else


			out( __(5)__ );


	}


	printf("%d%c", a % n + 1, " \n"[a == n + t]);


}


int main() {


	scanf("%d%d%d%d", &n, &m,&s,&t);


	s--, t--;


	for (int i = 0; i < m; i++) {


		int a, b, c;


		scanf("%d%d%d", &a, &b, &c);


		add(a - 1, b - 1, c);


	}


	solve();


	if (dis2[t] == inf)


		puts("-1");


	else {


		printf("%d\n", dis2[t]);


		out(n + t);


	}


	return 0;


}

选择题