Gideok_it

#include using namespace std; #define X first #define Y second int v, e, st,en; //{비용, 정점 번호} vector adj[20005]; const int INF = 1e9 + 10; int d[1005]; // 최단 거리 테이블 int pre[1005]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> v >> e; fill(d, d + v + 1, INF); while (e--) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({ w,v }); } cin >> st >> en; priority_queue pq; d[st] = 0; /..

다익스트라 알고리즘(1950년대) [ 알고리즘 설명 ] - 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 - 플로이드 알고리즘은 음수인 사이클만 아니면 음수인 간선이 있어도 작동하지만 다익스트라 알고리즘은 음수인 간선이 있으면 작동하지 않는다. ( 벨만포드 알고리즘을 사용하면 해결된다. ) - 길찾기 알고리즘으로 A*알고리즘이 있다. (내비게이션에서의 길 찾기처럼 100% 정확한 최단거리를 내지 않아도 되고 정점의 개수가 너무 많아 현실적으로 다익스트라 알고리즘을 사용할 수 없을 때 쓰는 근사 알고리즘이다) [ 구현 ] - 새로운 정점을 추가할 때 모든 정점에서 추가된 정점까지 거리를 확인하면 O(VE)가 되고 미리 거리를 계산해두고 거기서 최솟값을 찾는다면 O(V^2+E)가 되..

#include using namespace std; #define X first #define Y second int v, e, st; //{비용, 정점 번호} vector adj[20005]; const int INF = 1e9 + 10; int d[20005]; // 최단 거리 테이블 int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> v >> e >> st; fill(d, d + v + 1, INF); while (e--) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({ w,v }); } priority_queue pq; d[st] = 0; // 우선순위 큐에 {0, 시작점} 추가 pq.pus..

#include using namespace std; const int INF = 0x3f3f3f3f; int v[12][12]; int n, start; int a, b, c; int ans=INF; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> start; for (int i = 1; i >v[i][j]; } } for (int i = 0; i < n; i++) v[i][i] = 0; for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) v[i][j] = min(v[i][j], v[i][k] + v[k][j]); // if 문으로 바꾸..

#include using namespace std; const int INF = 0x3f3f3f3f; int v[205][205]; vector vv; int ans[205]; int n, e,kk; int a, b, c; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> e; for (int i = 1; i > a >> b >> c; v[a][b] = min(v[a][b], c); } for (int i = 1; i > kk; for (int i = 0; i > aa; vv.push_back(aa); } for (int k = 1; k