POJ 1734.Sightseeing trip(Floyd 최소 루프)
1495 단어 floyd
code
/*
floyd , , O(n^3)
*/
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 109, maxn = 252645135;
int g[INF][INF], dis[INF][INF], pre[INF][INF];
int ans[INF];
//pr[i][j] i j
int n, m, tem , tol;
int main() {
while (cin >> n >> m) {
tem = maxn;
memset (g, 0xf, sizeof g);
memset (dis, 0xf, sizeof dis);
memset (pre, 0, sizeof pre);
int x, y, z;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> z;
if (z < g[x][y])
dis[x][y] = dis[y][x] = g[x][y] = g[y][x] = z;
pre[x][y] = y, pre[y][x] = x;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++)
for (int j = i + 1; j < k; j++) {
if (tem > dis[i][j] + g[i][k] + g[k][j]) {
tem = dis[i][j] + g[i][k] + g[k][j];
int t = i;
tol = 0;
while (t != 0) {
ans[++tol] = t;
t = pre[t][j];
}
ans[++tol] = k;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && dis[i][k] + dis[k][j] < dis[i][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
pre[i][j] = pre[i][k];
}
}
if (tem == maxn) cout << "No solution.";
else
for (int i = 1; i <= tol; i++)
cout << ans[i] << ' ';
cout << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 11097번: 도시 계획입력된 그래프에서 SCC를 찾아서 묶고, 거기서 사이클 하나 만들어서 출력하고, 각 SCC에 속하는 노드 하나씩 뽑아서 u->v 출력하면 된다. 중복 간선을 제거할 때 위상정렬을 사용하려고 했는데 안됐다... i->...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.