Tävlingsprogrammering/Uppgifter/Jan Ersa och Per Persa

Jan Ersa och Per Persa

Så här börjar en dikt av Gustaf Fröding: Jan Ersa ägde Nackabyn, Per Persa ägde Backabyn i By i Västra Ed. Jan Ersa, Per Persa, de höllo aldrig fred.

När Jan Ersa och Per Persa, på äldre dagar, flyttade in till staden såg de till att de hamnade så långt från varandra som möjligt. Skriv ett program som läser in information om gatorna i staden och som sedan bestämmer mellan vilka två hus den kortaste vägen är som längst, samt längden av denna väg.

Kartan visar stadens alla hus och gator i exemplet. Vi ser också de röda husen där Jan Ersa och Per Persa numera bor. Dessa två hus (nr 1 och 9) är de hus i staden som ligger längst ifrån varandra (4900 meter). (I bilden saknas avstånd 10 mellan hus 7 och 10.)

Indata

På första raden står ett tal N, 2 ≤ N ≤ 100, som anger antalet hus i staden. Husen är numrerade från 1 till N. På nästa rad återfinns ett tal som anger antalet gator V, 2 ≤ V ≤ 500. Därefter följer V rader med tre tal på varje rad: från hus nummer, till hus nummer och gatans längd (givet i 100-tals meter). I givna indata går det alltid att ta sig från vilket hus som helst till vilket annat hus som helst.

Utdata

Programmet ska skriva ut en rad med tre tal åtskilda av blanksteg: Numren på de två husen längst ifrån varandra (det lägsta numret först) samt avståndet i meter. Om det finns flera par av städer som ligger på detta avstånd kan du ange vilket som helst av dem.

Exempel: Indata

15
27
1 12 10 
1 2 9 
2 12 9 
6 12 9 
3 6 9 
2 3 8 
3 12 10 
3 4 8 
4 13 6 
5 13 11 
5 6 8 
4 6 11 
4 5 15 
6 7 12 
7 8 8 
8 11 6 
9 11 11 
9 10 8 
7 10 10 
10 11 14 
8 15 11 
5 15 9 
5 7 13 
5 8 12 
5 14 12 
13 14 16
14 15 8 

Exempel: Utdata

1 9 4900

Lösning

Ett ganska standardproblem där man ska hitta kortaste vägen mellan samtliga noder (hus). Floyd-Warshalls algoritm löser detta snabbt och enkelt.

#include <cstdio>
#define INF 10000000

int N, V;

//Avståndet mellan två hus
int dist[100][100];

int main(){
	scanf("%d%d", &N, &V);
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			dist[i][j] = INF;
	for(int i=0; i<V; i++){
		int hus1, hus2, len;
		scanf("%d%d%d", &hus1, &hus2, &len);
		hus1--, hus2--;
		dist[hus1][hus2] = len;
		dist[hus2][hus1] = len;
	}
	//Floyd Warshall
	for(int k=0; k<N; k++)
		for(int i=0; i<N; i++)
			for(int j=0; j<N; j++){
				int tmp;
				if ((tmp = dist[i][k] + dist[k][j]) < dist[i][j]){
					dist[i][j] = dist[j][i] = tmp;
				}
			}
	//Hämta ut det paret som har längst kortast avstånd mellan sig
	int biggest = 0;
	int from;
	int to;
	for(int i=0; i<N-1; i++)
		for(int j=i+1; j<N; j++)
			if (dist[i][j] > biggest){
				biggest = dist[i][j];
				from = i;
				to = j;
			}
	printf("%d %d %d\n", from+1, to+1, biggest*100);
}