문제

s에서 e로 가는 문제인데 최단 경로를 피해서 도착할때 두번째 최단경로의 거리를 구하는 문제다.

접근

무작정 다익스트라로 접근하고나서 최단 거리를 어떻게 체크할지 고민이었다.

그래서 가이드 코드와 고민해본 결과
최단 거리를 저장하고 도착지점에서 시작점으로 거슬러가며 최단거리인지 체크해보는 것이다.

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));
크기는 byte 단위이므로 보통 sizeof를 써주면 된다.

memset 초기화 주의점

문제는 초기화 값인데 int 형으로 받지만 내부적으로 unsigned char로 변환해 char로 넣어줘도 된다.

중요한것은 초기화 단위가 byte라는 것이다.
그래서 32bit 메모리에서는 0x00000000 같이 나오는데 0x12로 초기화하면 0x12121212와 같이 나온다.

그래서 0으로 초기화는 그냥 0으로 하면되는데
int형 최대값으로 초기화하려면 int형 크기를 고려해야한다.

int는 4byte == 2^32bit다
16진수로 표기하면 0xffffffff이다.
여기서 signed int이므로 맨앞 비트는 부호로 사용한다.
그래서 절반 -1이 int 최대일것이다.
그러면 byte단위로 초기화한다면 0x7f가 최대가 될것이다.

결국 memset(arr,0x7f,sizeof(arr))와 같이 초기화하면 배열 값이 0x7f7f7f7f 으로 초기화된다.
10진수로 표현하면 약 2000000000 값이 나온다.

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]);
		}
	}
}