백준 1504, 특정한 최단 경로

문제

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

풀이

그냥 간단하게 다익스트라 알고리즘을 각각 적용해서 풀면 되는 문제 였다. 다만 다익스트라 알고리즘 구현에 자신이 없다보니 좀 쫄았는데구현 자체는 막 그렇게 어렵지 않은 것 같다. 다만 알고리즘을 보고 구현했고, 구현에 특정한 틀이 없으니 특정한 틀을 만드는 필요가 있어 보인다.

나머지는 딱히 말할 사항이 없다.

실수

• 다익스트라 알고리즘의 틀을 익히자
• 시간은 30분, 적당? 좀더 줄이자?

코드

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int v1, v2, n, e;
vector<vector<pair<int, int>>> graph(1000, vector<pair<int, int>>(0, make_pair(0, 0))); // (정점, 가중치)
vector<int> cost(1000, 0);
vector<int> visit(1000, 0);

int dijkstra(int a, int b) { // a to b

	// 초기화
	for (int i = 0; i < cost.size(); i++) {

		cost[i] = 3e8;
		visit[i] = 0;

	}

	cost[a] = 0; // 처음은 시작노드 선택
	
	for (int i = 1; i <= n; i++) {

		int min_index = 0;
		int min_num = 3e8;

		for (int j = 1; j <= n; j++) {

			if (min_num > cost[j] && visit[j] != 1) {

				min_num = cost[j];
				min_index = j;

			}

		}

		if (min_num == 3e8)
			break;

		visit[min_index] = 1;

		for (int j = 0; j < graph[min_index].size(); j++) {

			cost[graph[min_index][j].first] = min(cost[graph[min_index][j].first], cost[min_index] + graph[min_index][j].second);

		}


	}

	return cost[b];

}

int main() {

	int temp1, temp2, temp3;

	scanf("%d %d", &n, &e);

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

		scanf(" %d %d %d", &temp1, &temp2, &temp3);

		graph[temp1].push_back(make_pair(temp2, temp3));
		graph[temp2].push_back(make_pair(temp1, temp3));

	}

	scanf(" %d %d", &v1, &v2);

	int result = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n);
	result = min(result, dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, n));

	if (result >= 3e8) {

		printf("-1");

	}

	else
		printf("%d", result);

	return 0;


}