P10601 [NWERC 2006] Ticket to Ride

You are given a map with some cities. There may be routes connecting cities. To simplify, we use an undirected graph: each edge has a weight, meaning the cost to choose this edge. Given $4$ pairs of vertices (pairs may repeat), find a set of edges with the minimum total weight such that every given pair of vertices is connected using only the chosen edges.

The first line contains $2$ integers, $n$ and $m$, which represent the number of cities and the number of edges. The next $n$ lines each contain a string, the name of a city. Each city name is a string of lowercase letters of length at most $20$. The next $m$ lines each contain $s_1, s_2, w$, where $s_1$ and $s_2$ are city names, and $w$ is the weight of the edge between them. Finally, there are $4$ lines, each containing two strings, which are the names of a required pair of cities.

Output one line containing the minimum cost.

Constraints: $1\leq n\leq 30$, $0\leq m\leq 1000$, $1\leq w\leq 10000$. Translated by ChatGPT 5