记录编号	577309	评测结果	AAAAAAAAAA
题目名称	[POJ 1734]观光旅行	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-10-31 11:17:20	内存使用	0.00 MiB

#include "bits/stdc++.h"

using i64 = long long;

const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int a[N][N], dist[N][N], pos[N][N];
std::vector<int> path;

void get(int x, int y) {
    if (pos[x][y] == 0) return;
    get(x, pos[x][y]);
    path.emplace_back(pos[x][y]);
    get(pos[x][y], y);
}

int main() {
    freopen("sightseeingtrip.in", "r", stdin); 
    freopen("sightseeingtrip.out", "w", stdout);
    std::cin >> n >> m;
    memset(a, 0x3f, sizeof a);
    for (int i = 1; i <= n; ++ i) {
        a[i][i] = 0;
    }
    for (int i = 1; i <= m; ++ i) {
        int x, y, z;
        std::cin >> x >> y >> z;
        a[x][y] = a[y][x] = std::min(a[x][y], z);
    }
    memcpy(dist, a, sizeof dist);
    i64 ans = INF;
    for (int k = 1; k <= n; ++ k) {
        for (int i = 1; i < k; ++ i) {
            for (int j = i + 1; j < k; ++ j) {
                if ((i64) dist[i][j] + a[i][k] + a[k][j] < ans) {
                    ans = dist[i][j] + a[i][k] + a[k][j];
                    path.clear();
                    path.emplace_back(k);
                    path.emplace_back(i);
                    get(i, j);
                    path.emplace_back(j);
                }
            }
        }
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pos[i][j] = k;
                }
            }
        }
    }
    if (ans == INF) {
        std::cout << "No solution." << '\n';
    } else {
        for (int i : path) {
            std::cout << i << ' ';
        }
        std::cout << '\n';
    }
    return 0;
}