백준 1916(최소비용 구하기)

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

1916번: 최소비용 구하기

 

제발 문제좀 제대로 읽자. 조건을 제대로 파악해야 찾을 수 있다.

 

그냥 다 익스트라로 풀린다. priority_queue를 이용한 다 익스트라의 일반적인 시간복잡도는 O(ElogV)이고 이 문제에서는 

 

V = 1,000 E = 100,000 이므로 10^5로 간단하게 풀린다. 

 

1. 하지만 이전 문제에서의 문제와 같이 한 지점에서 다른 지점까지의 경로는 하나 이상일 수 있다. 

2. 경로의 비용은 0이상이다. (0일 수 있다)

 

2.의 조건 때문에 0이면 모두 INF로 초기화 해주는 코드를 수정해줘야 했다.

 

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
#define MAX 1001

priority_queue<pair<int, int> > pq;
pair<int, int> p;
int N, M, a, b, c, start, fin, INF = 987654321;
int city[MAX][MAX];
int dist[MAX];
bool visited[MAX];
bool checked[MAX][MAX];

void solve() {
	for (int i = 1; i <= N; i++) {
		pq.push(make_pair(-dist[i], i));
	}
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		if (!visited[p.second]) {
			visited[p.second] = true;
			for (int i = 1; i <= N; i++) {
				if (dist[i] > dist[p.second] + city[p.second][i]) {
					dist[i] = dist[p.second] + city[p.second][i];
					pq.push(make_pair(-dist[i], i));
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		if (city[a][b] > c || !checked[a][b]) {
			city[a][b] = c;
			checked[a][b] = true;
		}
	}
	cin >> start >> fin;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			if (!checked[i][j] && city[i][j] == 0) city[i][j] = INF;
		}
	}

	for (int i = 1; i <= N; i++) {
		if (start == i) continue;
		dist[i] = city[start][i];
	}
	solve();

	cout << dist[fin] << "\n";
}