What happened? Where is it? You wonder, waking up only to find yourself in a strange but familiar place. You look around, and the sign on the wall immediately reminds you where you are. The sign says “Aperture Science Enrichment Center”.
Hi Chell, glad to see you again. It is GLaDOS with her electronic voice. She seems excited to see you, You may wonder why you are here again. The truth is, after some failed trials, I finally realized that you are the one and only great test subject! Aperture Science needs you! You look frightened by her outburst. But she then goes back to a gentle, soft voice, Don't be afraid, all you need to do is complete some tests in some rooms, but this time you should make it as fast as possible. When all tests are done, you can have a cake as an award.
You don't know whether you can trust her, but you simply have no choice but to complete all tests as fast as possible. The Aperture Science Enrichment Center has nnn distinct rooms, labeled 1 through n . Thanks to recent developments in the years when you were absent, now you can directly go from any room i to room j (1≤i,j≤n) within time aij . You may assume that ai,j=0 for all 1≤i≤n and ai,j≥0 for all 1≤i,j≤n1 satisfying i≠j . Also, as there exist one-way elevators, gels, companion cubes, and bots, it could happen that ai,j≠aj, ,ifor i≠ji . GLaDOS has handed you a list of rooms v1,v2,…,vk (k≥2,1≤vi≤n) so that you need to sequentially visit the rooms in the list in order, to complete all tests as fast as possible. You are now in room v1 and are ready to take the first test at any time. As you are so familiar with all the tests, the time needed for you to complete each test can be ignored, and you only need to minimize the total time cost on the ways of visiting the rooms, which sounds easy enough.
Oh. I forgot to remind you, to make it easier for you but not too easy, you may look behind you. You turned around, and there is a portal gun in the box, but on the box, it says “Limited use: only use once before starting the tests”. With closer inspection, this portal gun creates portals not by shooting but by entering room numbers. The guideline lying next to it says that before trying to complete all tests, you are allowed to enter two numbers i,j such that 1≤i≤j≤n , then a two-way portal will be created between rooms i and j , so that you can directly move from either one to the other within no time, meaning setting ai,j=aj,i=0 . This choice of iii and jjj needs to be made before trying to complete all the tests and cannot be changed.
So you need to carefully choose the two rooms to open up a portal, then complete all tests as quickly as possible. What is the minimum time needed? Surely you can find out.