マトリックス乗算のテーマ2——bzoj 1706[usaco 2007 Nov]relays乳牛リレーの問題解

転載は明記してくださいhttp://blog.csdn.net/jiangshibiao/article/details/24960651
【原題】
1706:[usaco 2007 Nov]relays乳牛リレー
Time Limit: 5 Sec  
メモリLimit: 64 MB
Submit: 340  
Solved: 162
[Submit][Sttus]
Description
FJのN（2<=N==1,000,000）は彼女たちの日常運動種目としてリレー競走を選択しました。リレーの場所はもちろん牧場にあるT（2）<=T<=100）コースです。農場の滑走路にはいくつかの交差点があります。各滑走路はそれぞれ違った交差点を結んでいます。iとI 2_i（1<=I 1ガイ<=1,000；1<=I 2ガイ<=1,000）。各交差点は少なくとも二つの滑走路の端点です。牛たちは滑走路の長さを知っています。i（1<=lengthui<=1,000）と各滑走路を結ぶ交差点の番号、そして、どの2つの交差点が2つの異なる滑走路から直接つながっていません。これらの交差点と滑走路が図になっていると考えられます。リレーを完走するために、すべてのN頭の乳牛は走る前にある交差点に立ちます。もちろん、彼女たちの立ち位置は彼女たちがバトンを順次に伝達することができることを保証して、しかも最後に棒を持つ乳牛は予定の終点で止まる。あなたの任務は、プログラムを書いて、リレーの起点（S）と終点（E）が確定した場合、乳牛たちの走路の最小総延長を計算することです。この道はNコースを通ります。
Input
＊第1行：4個はスペースで区切られた整数：N，T，S，及びE
*2.T＋1行目：i＋1は3個でスペースで区切られた整数：length_i，I 1_i，及びI 2_i，i番目の滑走路を述べた。
Output
*1行目：正の整数を出力し、始点がS、終点がEであり、Nコースを通過する経路の最小長さを表します。
Sample Input
2 6 6 4 11 4 4 4 4 4 4 8 8 9 6 6 8 2 6 6 9 3 8 9 9
Sample Output
10
HINT
ソurce
Gold
【分析】これは裸のマトリクス掛け算です。N<=10^6に見えますが、実は100本の辺だけです。一つの辺は2つの点まで繋げることができますが、テーマの中では「各交差点は少なくとも2つの滑走路の端点です」と言っています。明らかに最大100点しかありません。先に離散してからマトリックスをかけてもいいです。
【PS】マトリクス掛け算が速い時、私のRES初値賦がよくなくなりました。いっそflagsをつけて記録しました。
【コード】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1010580540
using namespace std;
struct matrix
{
  int p[105][105],n;
  matrix(){memset(p,60,sizeof(p));}
}ans,a;
matrix operator * (matrix a,matrix b)
  {
    matrix c;c.n=a.n;
    for (int i=1;i<=a.n;i++)
      for (int j=1;j<=b.n;j++)
        for (int k=1;k<=a.n;k++)  
          c.p[i][j]=min(c.p[i][j],a.p[i][k]+b.p[k][j]);
    return c;
  }
int i,n,j,k,K,tot,x,y,z,s,e,m,dfs[1000005];
matrix quick(int b)
{
  matrix res;
  bool flag=true;
  while (b)
  {
    if (b&1) 
    {
      if (flag) 
      {
        flag=false;
        res=a;
      }
      else res=res*a;
    }
    b=b/2;a=a*a;
  }
  return res;
}
int get(int x)
{
  if (dfs[x]) return dfs[x];
  dfs[x]=++n;return n;
}
int main()
{
  scanf("%d%d%d%d",&K,&m,&s,&e);
  for (i=1;i<=m;i++)
  {
    scanf("%d%d%d",&z,&x,&y);
    x=get(x);y=get(y);
    a.p[x][y]=a.p[y][x]=z;
  }
  s=get(s);e=get(e);a.n=n;
  ans=quick(K);
  printf("%d",ans.p[s][e]);
  return 0;
}