uos-machine-learning

플로이드는 다익스트라로도 풀 수 있다. #include #include #include #include using namespace std; // dist[i][j] -> i에서 j로 가는 최단 경로 int dist[101][101]; bool visited[101]; int N, M; // 인접리스트 adj[i] = {(v1, x1), (v2, x2)} vector adj[101]; void dijkstra(int root) { dist[root][root] = 0; priority_queue q; q.push({ 0, root }); // visited 배열 초기화 memset(visited, 0, sizeof(visited)); while (!q.empty()) { int now = q.top()...

정점이 N개일 때 최단 경로는 항상 최대 N-1개로 구성되므로 N단계에서 최단경로가 갱신되면 음수로 되어있는 사이클이 존재한다. #include #include #include #include #include using namespace std; struct point{ int from; int to; int cost; }; int n, m, w; const int inf = 0x1fffffff; int main(){ int T; cin >> T; while (T--){ cin >> n; cin >> m; cin >> w; vector group; int dist[501]; for (int i = 1; i > u >> v >> x; group.push_back({ u, v, x }); group.push..

가중치에 음수가 있으므로 다익스트라가 아닌 벨만포드 알고리즘을 써야 한다. -10000 m; group.resize(m); for (int i = 0; i > group[i].now; cin >> group[i].next; cin >> group[i].cost; } for (int i = 1; i

인접행렬이 주어졌을 때 모든 정점 i, j 에 대하여 i에서 j로 가는 경로가 있는지 없는지 판단 For문으로 모든 정점의 추이관계를 찾아주면 된다. #include #include using namespace std; int d[100][100]; int main() { int n; cin >> n; for (int i=0; i d[i][j]; } } for (int k=0; k

dist[i][j] 는 i->j로 가는 최소 비용, 따라서 사이클은 dist[i][j] + dist[j][i]이다. 이중 최소값을 찾으면 된다. #include #include #include #include #include using namespace std; int N, M; vector graph; int answer[401][401]; vector dijkstra(int src){ vector dist(N + 1, INT_MAX); priority_queue q; q.push(make_pair(0, src)); dist[src] = 0; while (!q.empty()){ int nowcost = -q.top().first; int now = q.top().second; q.pop(); if (d..

다익스트라에서 dist 배열을 갱신할 때 마다 parent 배열에 연결된 노드를 저장하면 된다. #include #include #include #include #define INF 0x7fffffff; using namespace std; vector adj[1001]; // 최소 비용 저장 int dist[1001]; // 최소 비용을 갖는 부모 저장 int parent[1001]; // 경로에 포함된 도시 경로 개수 int cnt; bool visited[1001]; void dijkstra(int root) { dist[root] = 0; priority_queue q; q.push({ 0, root }); while (!q.empty()) { int now = q.top().second; q.p..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net N개의 도시가 있고 다른 도시에 도착하는 M개의 버스가 있을 때 A에서 B로 가는 최소비용을 출력하는 문제이다. 최단경로 알고리즘..

1 M; vector Edge; int ans = 0; for (int m = 0; m > a >> b >> c; Edge.push_back({ a, b, c }); } sort(Edge.begin(), Edge.end()); for (int i = 1; i