USACO 2.4.4 Bessie Come Home

構想:この問題はFloyedアルゴリズムを用いて任意の2点の距離を直接計算し,'Z'距離が最も遠く,牛が存在する牧区からZまでの距離に出力する.もう一つは,問題中のデータを隣接行列でどのように格納するかであり,アルファベットのASCII-‘A’を隣接行列の下付き文字とすることができる.
Floyedアルゴリズムの補完
Floyd-Warshallアルゴリズムは、各ペアのポイント間の最短距離を見つけるために使用されます.エッジを隣接行列で格納する必要があり,このアルゴリズムは最適サブパスを考慮することによって最適パスを得る.
注意個々のエッジのパスも必ずしも最適なパスではありません.

は、任意の片側パスから開始します.すべての2点間の距離はエッジの重み、または無限大であり、2点間にエッジが接続されていない場合.

は、各ペアの頂点uおよびvについて、uからwへ、およびvへの経路が既知の経路よりも短くなるように、1つの頂点wが存在するかどうかを見る.更新する場合.

不思議なことに、適当に並べば結果が得られます.

// dist(i,j)     i   j     
For i←1 to n do
   For j←1 to n do
      dist(i,j) = weight(i,j) 
 
For k←1 to n do // k “    ”
  For i←1 to n do
    if (i<>k) then
      For j←1 to n do
        if (i<>j) and(k<>j)then
          if (dist(i,k) + dist(k,j) < dist(i,j)) then //         ？
              dist(i,j) = dist(i,k) + dist(k,j)

このアルゴリズムの効率はO(
V3).図を格納するために隣接行列が必要です.
ソース:

/*
ID: supersnow0622
PROG: test
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
 
using namespace std;
int dist[101][101];
int main() {
    ofstream fout ("test.out");
    ifstream fin ("test.in");
    int P;
    cin>>P;
    char a,b;
    int c;
    for(int i=0;i<101;i++)
      for(int j=0;j<101;j++)
        dist[i][j]=1000000;
    for(int i=0;i<P;i++)
    {
      cin>>a>>b>>c;
      if(c<dist[a-'A'][b-'A'])
      {
        dist[a-'A'][b-'A']=c;
        dist[b-'A'][a-'A']=c;
      }
    }
    for(int k=0;k<60;k++)
      for(int i=0;i<60;i++)
       if(i!=k)
       {
         for(int j=0;j<60;j++)
          {
           if(i!=j&&k!=j)
             if(dist[i][k]+dist[k][j]<dist[i][j])
                dist[i][j]=dist[i][k]+dist[k][j];
          }
       }
    int min=1000000,record;
    for(int i=0;i<25;i++)
       if(dist[i][25]<min)
        {
          min=dist[i][25];
          record=i;
        }
    cout<<(char)(record+'A')<<" "<<min;
    return 0;
}