글 읽기 - 반례 질문드립니다

devbelly 4년 전 0

접근 방식은 방문해야만 하는 특정 노드를 우선순위 큐에서 pop하게된다면, 그 노드를 다시 시작지점으로 잡아서 목표노드까지

길을 찾는 방식으로 구현하였습니다

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
typedef long long ll;
typedef pair<ll, ll> p;

ll dist[801];
vector<p> adj[801];
priority_queue<p, vector<p>, greater<p>> pq;


int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios::sync_with_stdio(false);

	int N, E; // 노드의수 N, 정점의수 E
	cin >> N >> E; // 를 입력받자
	fill(dist, dist + 801, INF); 


	for (int i = 0;i < E;++i) { //무방향 인접리스트를 만들자
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].emplace_back(w, v);
		adj[v].emplace_back(w, u);
	}
	int U, V; // 방문해야만 하는 두개의 노드
	cin >> U >> V; // 를 입력받자

	bool flag = true; // U를 한번 방문하기 위한 용도
	bool flag2 = true; // V를 한번 방문하기 위한 용도

	dist[1] = 0;
	pq.push({ 0,1 }); // 1번 노드까지 가기위해 0의 COST가 필요. 시작값
	while (!pq.empty()) { 
		auto [cost, node] = pq.top(); 
		pq.pop();
		if ((node == U)&&flag) { // 뽑은 NODE가 U 라면 (if는 u를 시작지점으로 만들어주는 구간)
			
			flag = false; // 다시는 리셋안하기 위해 false로 바꿔주자
			while (!pq.empty()) // 기존에 pq안에 있는거 싹 제거
				pq.pop();
			pq.push({ dist[node],node }); // U를 초깃값으로 만들자
			ll temp = dist[node];
			fill(dist, dist + 801, INF);
			dist[node] = temp; // 1번에서 U까지 가야하는 값은 기억해야하므로 dist[U]는 0으로 리셋하지말자
		}
		if ((node == V)&& flag2) { // 위에 U노드 리셋과 마찬가지과정
			/*cout << 2;*/
			flag2 = false;
			while (!pq.empty())
				pq.pop();
			pq.push({ dist[node],node });
			ll temp = dist[node];
			fill(dist, dist + 801, INF);
			dist[node] = temp;
		}
		if (node == N && !flag && !flag2) { // !flag와 !flag2는 U,V를 방문했다는 증거 + 도착지점 N에 도달
			
			break; // 멈추기
		}	
		if (dist[node] < cost) continue; // 평범한 다익스트라 구현
		for (int i = 0;i < adj[node].size();++i) {
			auto [nextCost, next] = adj[node][i];
			if (dist[next] > cost + nextCost) {
				dist[next] = cost + nextCost;
				pq.push({ dist[next],next });
			}
		}
	}
	//for (int i = 1;i <= N;++i) // 
	//	cout << dist[i] << ' ';
	if (flag||flag2||dist[N]==INF) cout << -1; // 두개의 노드를 다 방문하지 않았거나 N을 방문할수 없으면 -1
	else cout << dist[N]; // 아니면 그 값을 출력하자

	return 0;
}

cozyyg 4년 전 4

다익스트라 알고리즘을 돌리면서 U라는 점이 먼저 등장했다 하더라도, V를 먼저 방문하는 것이 최적의 경로일 수 있습니다.

반례는 다음과 같습니다.

5
2 10
3 11
3 20
4 30
4 100
3

// answer: 61(1->3->2->4, 11+20+30)
// output: 80(1->2->3->2->4, 10+20+20+30)

devbelly 4년 전 0

너무 감사드립니다 덕분에 문제해결했습니다!!😃

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 질문드립니다

devbelly 4년 전 0

cozyyg 4년 전 4

devbelly 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말