제출 #1175728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175728		tkm_algorithms	즐거운 행로 (APIO20_fun)	C++20	0 / 100	0 ms	328 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 501;
int p[N][N];

vector<int> createFunTour(int n, int q) {
	vector<int> g[n+1];

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)p[i][j] = N;

	for (int i = 0; i < n; ++i) {
		p[i][i] = 0;
		for (int j = i+1; j < n; ++j) {
			int w = hoursRequired(i, j);
			if (w == 1) {
				g[i].push_back(j), g[j].push_back(i);
				p[i][j] = 1;
				p[j][i] = 1;
			}
		}
	}


	vector<pair<int, int>> m[n+1];

	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) 
			for (int j = 0; j < n; ++j) {
				p[i][j] = min(p[i][j], p[i][k] + p[j][k]);
			}
	}

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			m[i].push_back({p[i][j], j});

	for (int i = 0; i < n; ++i)sort(m[i].rbegin(), m[i].rend());

	vector<int> vis(n, 0);
	
	int last = 0, w = m[0][0].first;
	for (int i = 1; i < n; ++i) {
		if (m[i][0].first > w) {
			last = i, w = m[i][0].first; 
		}
	}
	// for (int)
	vector<int> ans;
	ans.push_back(last);
	ans.push_back(m[last][0].second);

	vis[last] = 1, vis[m[last][0].second] = 1;
	int lastw = m[last][0].first; 
	last = m[last][0].second;

	while (ans.size() < n) {
		for (auto i: m[last]) {
			if (vis[i.second] == 0 && i.first <= lastw) {
				ans.push_back(i.second);
				lastw = i.first, last = i.second;
				break;
			}
		}
	}

	return ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34