[백준 1504] 특정한 최단 경로

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

요구사항

1에서 n으로 도달하는데 v1,v2를 거쳐서 도달하는 최소 이동 경로 구하기

 

풀이

1 -> v1 -> v2 ->n

1 -> v2 -> v1 ->n

의 두가지의 최소경로가 있다

1-> v1 최소경로

v1 ->v2 최소경로

v2, v1->n 최소경로를 각 각 구하여 최소 값을 출력한다.

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
struct go {
	int x;
	int y;
};
int n, m;
const int INF = 0x7fffffff;
vector<go> v[801];
int startnode;
int endnode;
int Sdist[801];
int N1dist[801];
int N2dist[801];

void dik(int arr[],int start) {
	for (int i = 1; i <= n; i++) {
		arr[i] = INF;
	}
	arr[start] = 0;
	priority_queue<pair<int,int>> q;
	q.push({ 0,start });
	while (!q.empty()) {
		int Nowdist = -q.top().first;
		int Nowpos = q.top().second;
		q.pop();

		for (int i = 0; i < v[Nowpos].size(); i++) {
			int next = v[Nowpos][i].x;
			int nextdist = Nowdist+v[Nowpos][i].y;

			if (nextdist < arr[next]) {
				arr[next] = nextdist;
				q.push({ -nextdist,next });
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y,z;
		scanf("%d%d%d", &x, &y, &z);
		v[x].push_back({ y,z });
		v[y].push_back({ x,z });
		int zx;
		int asdf;
	}
	cin >> startnode >> endnode;
	dik(Sdist, 1);
	dik(N1dist, startnode);
	dik(N2dist, endnode);
	int ans1 = Sdist[startnode] + N1dist[endnode] + N2dist[n];
	int ans2 = Sdist[endnode] + N2dist[startnode] + N1dist[n];
	if (Sdist[startnode] == INF || Sdist[endnode] == INF || Sdist[n] == INF ||
		N1dist[1] == INF || N1dist[endnode] == INF || N1dist[n] == INF ||
		N2dist[1] == INF || N2dist[startnode] == INF || N2dist[n] == INF)
	{
		//cout << Sdist[startnode] << " " << Sdist[endnode] << " " << Sdist[n] << endl;
		//cout << N1dist[1] << " " << N1dist[endnode] << " " << N1dist[n] << endl;
		//cout << N2dist[1] << " " << N2dist[startnode] << " " << N2dist[n] << endl;

		cout << "-1" << endl;
	}
	else {
		ans1 = min(ans1, ans2);
		cout << ans1 << endl;
	}

	
	


}