neoevoke » [usaco] 2.4 Bessie Come Home

[usaco] 2.4 Bessie Come Home - usaco

2009.09.07 20:34 neoevoke Edit

최단거리를 찾는 문제이기 때문에

간단히 플로이드 워셜 알고리즘으로 풀 수 있는 문제이다.

하지만 복병이 있었으니...

입력 길이 하나 이상이라고 문제에 적혀있다.

둘 중 작은 값으로 정해주면 답이 나온다.

/*
ID: neoevok1
PROG: comehome
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>

using namespace std;

int dp[100][100];
int maxint=9999999;

int main() {
    ofstream fout ("comehome.out");
    ifstream fin ("comehome.in");

for(int i=0;i<100;i++)
		for(int j=0;j<100;j++)
			dp[i][j]=maxint;

int n;
    fin >> n ;
    
    string strline;
	getline(fin, strline);
    for(int i=0;i<n;i++)
	{
		getline(fin, strline);
		istringstream iss(strline);
		char l=' ',r=' ';

while(l==' ')
			iss >> l;
		while(r==' ')
			iss >> r;

int distance;
		iss >> distance;

int lindex=0, rindex=0;
		if(l<='Z') lindex=l-'A';
		if(l>'Z') lindex=l-'a'+26;
		if(r<='Z') rindex=r-'A';
		if(r>'Z') rindex=r-'a'+26;
		dp[lindex][rindex]=min(distance,dp[lindex][rindex]);
		dp[rindex][lindex]=min(distance,dp[rindex][lindex]);
	}

for(int k=0;k<52;k++)
		for(int i=0;i<52;i++)
			for(int j=0;j<52;j++)
			{
				if(	dp[i][j]>dp[i][k]+dp[k][j])
				{
					dp[i][j]=dp[i][k]+dp[k][j];
				}
			}

int m=maxint;
	int mindex;
	for(int i=0;i<25;i++)
	{
		if(m>dp[i][25]) 
		{
			m=dp[i][25];
			mindex=i;
		}
	}
		
	fout << (char)(mindex+'A') << " " << m << endl;
	
	return 0;
}

[usaco] 2.4 Fractions to Decimals [usaco] 2.4 Cow Tours

Trackbacks 0

엮인글 주소: http://dw.yutar.net/329486/95c/trackback

Comments 0

Leave Comments

neoevoke소셜계의 김성모

[usaco] 2.4 Bessie Come Home - usaco

Trackbacks 0

Comments 0

Leave Comments

Category

Recent Post

Recent Comment

Recent Trackback

Tag