What to do when garbage collector is slow?

I have a program that, to all appearances, is behaving properly. It uses very little memory to run, it has the profile I would expect looking at +RTS -hc. I have no reason to believe there is a memory leak (in the sense that it's not lazily holding on to things it no longer needs or strictly generating things it doesn't need yet). But it's slow, and according to -sstderr, most of the time is spent garbage-collecting. Why is the garbage-collector consuming so much running time? How can I deal with it? The program is a solution to this problem: https://open.kattis.com/problems/tourist The input data can be found here: http://heim.ifi.uio.no/~db/nm-i-programmering/nm2004/testdata/h.in