https://www.acmicpc.net/problem/1504 반드시 거쳐야 하는 두 개의 정점을 a,b라 하면 1->a->b->n 의 최단 경로와 1->b->a->n의 최단 경로의 길이 중 더 작은 것이 답이다. 각각 다익스트라를 3번씩 돌려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #define INF 800001using namespace std; int n,m,u,v,w,a,b,p1,p2,ans;vector adj[801]; int dijkstra(int s,int e){ vector dist..
https://www.acmicpc.net/problem/1753 다익스트라 (Dijkstra) 알고리즘은 모든 간선의 가중치가 음수가 아닌 그래프에서 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 가중치가 모두 같다면 BFS로 최단거리를 구할 수 있다. 먼저 시작점으로 부터의 최단거리를 나타내는 dist 배열을 할당하고 INF로 초기화한다. 일단 시작점의 최단거리가 0임은 알 수 있다. 그 다음 우선순위 큐(최소힙)을 이용하여 지금까지 구한 정점까지의 거리 중 최소값을 빼면서 인접 정점들을 검사한다. dist 값이 갱신될 때마다 큐에 (지금까지 찾은 최단거리,정점)을 넣어준다. 이 과정을 반복하다보면 시작점으로부터 다른 모든 정점까지의 최단거리에 해당하는 간선들로 이루어진 스패닝 트..