usaco_comehome.cpp

来自「usaco自己做的1到5章的代码」· C++ 代码 · 共 61 行

/*
ID: wangyuc2
PROG: comehome
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <cstring>
#include <memory>
#include <queue>
#define MAXLENGTH 2000000
using namespace std;
ifstream fin("comehome.in");
ofstream fout("comehome.out");

int main()
{
    int i,j,k,max,n,min;
    char pas1,pas2;
    bool cow_in[26];
    int a[52][52];
    for(i=0;i<52;i++)
      for(j=0;j<52;j++)
	  {if(i == j) a[i][j]=0;
	  else a[i][j]=MAXLENGTH;
	  }   
    memset(cow_in,false,sizeof(cow_in));
    fin>>n;
    max=MAXLENGTH;
    for(i=0;i<n;i++)
    {
       fin>>pas1>>pas2>>k;
	   if(pas1 == pas2) continue;
       if(pas1 <= 'Z' && pas1>='A') {pas1-=65;cow_in[pas1]=true;}
       else pas1=pas1-97+26;
       if(pas2 <= 'Z' && pas2>='A') {pas2-=65;cow_in[pas2]=true;}
       else pas2=pas2-97+26;
	   
       if(k<a[pas1][pas2]) a[pas1][pas2]=k;
       if(k<a[pas2][pas1]) a[pas2][pas1]=k;
    }
	cow_in[25]=false;
    for(k=0;k<52;k++)
      for(i=0;i<52;i++)
      { 
	     if(i == j) continue;
        for(j=0;j<52;j++)
        {
			if(i==k || j==k ) continue;
			 if(a[i][j]>a[i][k]+a[k][j]) 
			 {a[i][j]=a[i][k]+a[k][j];a[j][i]=a[i][j];}
         }
      }
      min=0;
    for(i=1;i<25;i++)
      if(cow_in[i] && a[i][25]<a[min][25]) min=i;
    fout<<char(min+65)<<' '<<a[min][25]<<endl;
   // system("PAUSE");
    return 0;
}