Mr. Worldwide — MetaCTF

Description

Please help! I'm a tour guide, and I need to tell my clients the minimum number of miles they need to travel to different cities to reach all their goals. They're really on me, so you have to do it FAST! The first number given is the number of nodes in the graph, and the rest of the numbers is an adjacency matrix of the graph, where each index represents the distance between the 2 correspondings nodes of the graph.

The service at nc nc.umbccd.net 23456 sends n = 20, then a 20 x 20 weighted adjacency matrix, and finally prompts for the minimum tour distance. The matrix is different on each connection, so the solve must parse the fresh instance and answer immediately.

One note worth preserving: the challenge was tracked locally under MetaCTF, but the returned flag used a DawgCTF format. I kept the event metadata as metactf to match the workspace and existing notes, and recorded the flag exactly as returned by the service.

Analysis

The keywords tour, cities, and adjacency matrix are the giveaway. This is a minimum Hamiltonian cycle problem: start at a city, visit every city exactly once, and return to the start with minimum total cost.

Because the graph is given as a complete weighted adjacency matrix and the prompt asks for the minimum tour distance, this is the classic Traveling Salesman Problem rather than a shortest-path or MST task.

The important parameters were:

• n = 20
• full weighted adjacency matrix
• remote instance changes every connection
• strict time limit

...