[백준/BOJ] 17096 Tourist C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/17096

[설명]
시간을 가장 적게 쓰면서 사진을 적게 찍는 경우를 찾는 문제이다. 일단 조건 상 1번 도시로부터 각 도시로의 시간을 가장 적게 쓰는 경로를 찾아야 한다. 아래와 같은 상황을 가정해보자.
5 6
1 2 10
1 3 20
2 4 20
3 4 10
2 5 20
3 5 10
1->2->4,5 / 1->3->4,5

1번 도시에서 2번, 3번 도시를 거쳐 4번, 5번 도시 각각에 도달하는 경로의 시간을 같다. 하지만 사진을 찍는 횟수를 생각했을 때 전자의 경우 50, 후자의 경우 40이므로 후자의 경우를 선택해야 한다. 즉, 시간이 같을 경우 직전 도시에서 현 도시로의 시간이 짧게 걸리는 것을 택하도록 하면 된다.

[코드]

#include<iostream>
#include<vector>
#include<queue>
#define ll long long
#define INF 250000000001
using namespace std;

struct info {
	int x;
	ll dis;
};

struct cmp {
	bool operator()(const info& a, const info& b) {
		return a.dis > b.dis;
	}
};

vector<info> graph[500001];
priority_queue<info, vector<info>, cmp> pq;
ll dis[500001], path[500001];
int N, M, path_cnt[500001];

void init() {
	for (int i = 1; i <= N; i++) dis[i] = INF;
}

void dijkstra() {
	init();
	int x;
	ll dist;
	dis[1] = 0;
	pq.push({ 1,0 });
	while (!pq.empty()) {
		x = pq.top().x;
		dist = pq.top().dis;
		pq.pop();
		if (dist > dis[x]) continue;
		for (auto& iter : graph[x]) {
			if (dis[iter.x] > iter.dis + dist) {
				path[iter.x] = iter.dis;
				dis[iter.x] = iter.dis + dist;
				pq.push({ iter.x,dis[iter.x] });
			}
			else if (dis[iter.x] == iter.dis + dist && path[iter.x] > iter.dis) path[iter.x] = iter.dis;
		}
	}
}

void ans() {
	ll answer = 0;
	for (int i = 2; i <= N; i++) answer += path[i];
	cout << answer;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int a, b; cin >> N >> M;
	ll c;
	while (M--) {
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
		graph[b].push_back({ a,c });
	}
	dijkstra();
	ans();
}