質問する

sからeまでの問題で,最短経路到達を避ける際に2番目の最短経路の距離を求める問題である.

に近づく

無計画にエストラに近づいた後、最短距離をどうチェックするか悩んだ.

だからマニュアルと結果を考えてみました.
最短距離を保存し、到達点から始点まで遡り、最短距離かどうかをチェックします.

for (info next : re_graph[now.to]) {
	// 최단 경로에 포함된다면
	if (now.cost + next.cost + dist[next.to] == dist[e]) {
		// 최단 경로 체크
		is_near_dist[next.to][now.to] = true;
		que.push({ next.to,now.cost + next.cost });
	}
}

memset

memset関数はあまり使わず、繰り返し文で初期化します.
複数回のテストを経て、入力が非常に多く、メモリ単位で初期化されたmemsetを使用しました.
検索結果
memory.hまたはstring.hライブラリを使用する必要があります.
使い方は以下の通りです.
memset(ホームアドレス、初期化値、サイズ)
ex) memset(arr,0,sizeof(arr));
サイズはバイト単位で、通常はsizeofを書くだけです.

memset初期化注意点

問題は初期化値がint型であるが,内部は符号なしcharに変換してcharを入れることができる.
重要なのは初期化単位がbyteであることです.
したがって、32 bitメモリには0 x 00000000と表示され、初期化が0 x 12であれば0 x 121,2212と表示される.
だから0に初期化すればいいです.
int型最大値に初期化するには、int型サイズを考慮する必要があります.
intは4 byte=2^32 bit
16進数で表すと0 xffffffffです.
ここではsigned intなので、前の方が記号として使われます.
したがって、半分-1はintの最大値であるべきです.
バイト単位で初期化すると0 x 7 fが最大値となります.
最終的にmemset(arr,0 x 7 f,sizeof(arr)のように初期化すると、アレイ値は0 x 7 f 7 f 7 f 7 fに初期化される.
十進法で表すと、約20,000,000,000,000,000,000,000,000です.

code

#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;

#define INF 0x7f7f7f7f
#define N_MAX 500
struct info {
	int to;
	int cost;
};
struct cost_cmp {
	bool operator()(info& a, info& b) {
		return a.cost > b.cost;
	}
};
int n, m, s, e, dist[N_MAX];
vector<info> graph[N_MAX],re_graph[N_MAX];
bool is_near_dist[N_MAX][N_MAX];

void dijkstra(int start) {
	priority_queue<info, vector<info>, cost_cmp> pq;
	// init dist
	memset(dist, 0x7f, n*sizeof(int));
	dist[start] = 0;
	pq.push({start,0});
	while (!pq.empty()) {
		info now = pq.top(); pq.pop();
		if (dist[now.to] < now.cost) continue;
		for (info next : graph[now.to]) {
			int new_cost = dist[now.to] + next.cost;
			if (new_cost < dist[next.to]) {
				dist[next.to] = new_cost;
				pq.push({ next.to,new_cost });
			}
		}
	}
}
void get_near_dist() {
	queue<info> que;
	que.push({e,0});
	bool visited[N_MAX];
	memset(visited, 0, N_MAX);
	// init near dist
	for (int i = 0; i < n; i++) {
		memset(is_near_dist[i], 0, n);
	}
	while (!que.empty()) {
		info now = que.front(); que.pop();
		if (visited[now.to]) continue;
		visited[now.to] = true;
		for (info next : re_graph[now.to]) {
			// 최단 경로에 포함된다면
			if (now.cost + next.cost + dist[next.to] == dist[e]) {
				// 최단 경로 체크
				is_near_dist[next.to][now.to] = true;
				que.push({ next.to,now.cost + next.cost });
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifdef _DEBUG
	freopen("B5719.in", "r", stdin);
	freopen("B5719.out", "w", stdout);
#endif
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0) return 0;
		cin >> s >> e;
		// init graph
		for (int i = 0; i < n; i++) graph[i].clear(), re_graph[i].clear();
		for (int i = 0; i < m; i++) {
			int a, b, c; cin >> a >> b >> c;
			graph[a].push_back({ b,c });
			re_graph[b].push_back({ a,c });
		}
		// dijkstra
		dijkstra(s);
#ifdef _DEBUG
		// distance
		/*printf("[dist] ");
		for (int i = 0; i < n; i++) {
			printf("(%d,%d) ", i, dist[i]);
		}
		printf("\n");*/
#endif
		// 최단 경로가 없는 경우
		if (dist[e] == INF) {
			printf("-1\n");
			continue;
		}
		// 최단경로 구함
		get_near_dist();
		// 최단경로를 무한으로 바꿈
		for (int a = 0; a < n; a++) {
			if (graph[a].empty()) continue;
			for (int i = 0; i < graph[a].size();i++) {
				info node = graph[a][i];
				if (is_near_dist[a][node.to]) {
					graph[a][i].cost = INF;
				}
			}
		}
		// 새롭게 다익스트라
		dijkstra(s);
#ifdef _DEBUG
		// distance
		/*printf("[dist] ");
		for (int i = 0; i < n; i++) {
			printf("(%d,%d) ", i, dist[i]);
		}
		printf("\n");*/
#endif
		// 답 출력
		if (dist[e] == INF) {
			printf("-1\n");
			continue;
		}
		else {
			printf("%d\n", dist[e]);
		}
	}
}