SW Expert Academy 1795 - 인수의 생일 파티

문제 링크

---

-

문제 해결

---

 1. 단방향 그래프를 입력받고, 1부터 N까지의 임의의 점에서 K까지의 최단거리와 K부터 임의의 점까지의 최단거리의 합 중에서 가장 큰 값을 구하는 문제.

 2. 다익스트라 알고리즘으로 문제 해결.

주의할 점 || 생각해볼 점

---

 1. 최대 간선의 수(N)가 10,000개, 최대 정점의 수(M)가 1,000개. 1부터 N까지의 임의의 수 전부에서 최단거리를 구하려면 시간복잡도 에 의해서 아슬아슬해진다. 그러므로 입력 받을 때, 정방향과 반대방향 인접리스트를 두 개 만들어서 K에서 다익스트라 알고리즘을 두 번 수행하면 된다.

 

참고

---

 - 다익스트라 알고리즘 visual code : https://www.swexpertacademy.com/main/visualcode/main.do#/home/mainlayout

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<iostream>
	#include<cstdio>
	#include<map>
	#include<string>
	#include<cstring>
	#include<algorithm>
	#include<queue>
	#include<set>
	#include<ctime>
	using namespace std;
	int N,M,K,T,u,v,w;
	vector<pair<int,int> > graph1[1003],graph2[1003];
	int dist1[1003],dist2[1003];
	// caution 1
	void djikstra(){
	for(int i=1;i<=N;i++){
	dist1[i]=dist2[i]=1e8;
	}
	dist1[K]=dist2[K]=0;
	priority_queue<pair<int,int> > pq1,pq2;
	pq1.push({0,K});
	pq2.push({0,K});
	while(!pq1.empty()){
	int here = pq1.top().second;
	int cost = -pq1.top().first;
	pq1.pop();
	if(dist1[here]<cost)
	continue;
	for(int i=0;i<graph1[here].size();i++){
	int there = graph1[here][i].first;
	int nextDist = graph1[here][i].second+cost;
	if(dist1[there]>nextDist){
	dist1[there]=nextDist;
	pq1.push({-nextDist,there});
	}
	}
	}
	while(!pq2.empty()){
	int here = pq2.top().second;
	int cost = -pq2.top().first;
	pq2.pop();
	if(dist2[here]<cost)
	continue;
	for(int i=0;i<graph2[here].size();i++){
	int there = graph2[here][i].first;
	int nextDist = graph2[here][i].second+cost;
	if(dist2[there]>nextDist){
	dist2[there]=nextDist;
	pq2.push({-nextDist,there});
	}
	}
	}
	}
	int main(){
	cin >> T;
	for(int z=1;z<=T;z++){
	memset(graph1,0,sizeof(graph1));
	memset(graph2,0,sizeof(graph2));
	cin >> N >> M >> K;
	for(int i=0;i<M;i++){
	scanf("%d %d %d",&u,&v,&w);
	graph1[u].push_back({v,w});
	graph2[v].push_back({u,w});
	}
	djikstra();
	int ans = -1;
	for(int i=1;i<=N;i++){
	ans=max(ans,dist1[i]+dist2[i]);
	}
	printf("#%d %d\n",z,ans);
	}
	return 0;
	}

view raw SW Expert Academy 1795.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.