Home > Old Blog Posts > USACO 2.4.4 Bessie Come Home

USACO 2.4.4 Bessie Come Home


数据范围这么小,不用floyd算法用什么?

代码:

/*
ID: dementr1
PROG: comehome
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“comehome.in”);
ofstream fout(“comehome.out”);
int dis[100][100]={},P;
void init()
{
int i,j,tmp;
char a,b;
for(i=0;i<52;i++)
for(j=0;j<52;j++)
dis[i][j]=100000;
fin>>P;
for(i=0;i<P;i++)
{
fin>>a>>b;
if(‘a'<=a&&a<=’z’) a=a-‘a’;
else if(‘A'<=a&&a<=’Z’) a=a-‘A’+26;
if(‘a'<=b&&b<=’z’) b=b-‘a’;
else if(‘A'<=b&&b<=’Z’) b=b-‘A’+26;
fin>>tmp;
if(tmp<dis[a][b]) dis[a][b]=dis[b][a]=tmp;
}
}
void floyd()
{
int k,i,j,min=10000000,mini;
for(k=0;k<52;k++)
for(i=0;i<52;i++)
for(j=0;j<52;j++)
if(i!=k&&k!=j&&i!=j&&dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
for(i=26;i<51;i++)
if(dis[51][i]<min)
{
min=dis[51][i];
mini=i;
}
fout<<(char)(mini+’A’-26)<<” “<<min<<endl;
}
int main()
{
init();
floyd();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: