백준 1916번 _ 최소비용 구하기

2020-04-26 · 배운 것 · 2분 읽기

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

1916번: 최소비용 구하기

풀이방법

기본적인 다익스트라 알고리즘을 사용하면 풀린다.

전체코드

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

#define Limit 987654321

using namespace std;
vector<vector<pair<int, int>>> bus;
int costs[1001];
int N, M;

void Input()
{
	cin >> N;
	cin >> M;
	bus.resize(N+1);
	int s, e, c;
	for (int i = 0; i < M; i++)
	{
		cin >> s >> e >> c;
		bus[s].push_back({ e, c });
	}
	
}

void dijstraInit(int start)
{
	for (int i = 1; i <= N; i++)
		costs[i] = Limit;
	costs[start] = 0;
}

queue<int> que;
void dijstra(int here)
{
	for (auto& ele : bus[here])
	{
		int next = ele.first;
		int cost = ele.second;

		//바뀐건 큐에 넣기
		if (costs[next] > costs[here] + cost)
		{
			costs[next] = costs[here] + cost;
			que.push(next);
		}
	}
	if (!que.empty())
	{
		int next = que.front();
		que.pop();
		dijstra(next);
	}
}

void solve()
{
	int start, arrived;
	cin >> start >> arrived;
	dijstraInit(start);

	//dijstra
	dijstra(start);

	cout << costs[arrived];
}

int main()
{
	Input();
	solve();
	return 0;
}

후기

요즘 계속 시뮬레이션 문제만 풀었더니 최단거리 알고리즘들이 기억이 안나서 기본적인 문제를 한번 풀어보았다.