這題面是外星人寫的吧

定義一個群，其元素為一個矩陣，定義一個該群的元素M，并且M存著一個圖。

定義一個二元運算符*，運算結果仍為該群的元素。

如M*M=R，則R（i，j）=Min（Rij，Mik+Mkj）

這個操作滿足交換律和結合律。

其意義代表不言而喻。（手動滑稽）

因此可利用快速冪求解。

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int MOD=1000; const int sz=201; int N,t,s,e,n; struct mat{int a[sz][sz];mat(){memset(a,0,sizeof a);}void initE(){for(int i=0;i<n;i++)a[i][i]=1;}void initfib(){a[1][0]=a[0][1]=a[0][0]=1;a[1][1]=0;}mat operator*(const mat&t)const{mat q;memset(q.a,0x3f,sizeof q.a);for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)q.a[i][j]=min(q.a[i][j],a[i][k]+t.a[k][j]);return q;}void out(){for(int i=0;i<n;i++){for(int j=0;j<n;j++)printf("%d ",a[i][j]);printf("\n");}}mat operator^(int k)const{mat res=*this;mat m=*this;//res.out();m.out();while(k>0){if(k&1)res=res*m;m=m*m;k>>=1;}return res;}}; int mp[1010]; int main(){ scanf("%d%d%d%d",&N,&t,&s,&e);n=0;for(int i=0;i<1010;i++)mp[i]=-1;mat m;memset(m.a,0x3f,sizeof m.a);while(t--){int l,x,y;scanf("%d%d%d",&l,&x,&y);int sx=mp[x],sy=mp[y];if(sx==-1)sx=mp[x]=n++;if(sy==-1)sy=mp[y]=n++;m.a[sx][sy]=m.a[sy][sx]=l;}// m.out();m=m^(N-1);// m.out();printf("%d\n",m.a[mp[s]][mp[e]]);return 0; }

?

轉載于:https://www.cnblogs.com/MeowMeowMeow/p/7640275.html

總結

以上是生活随笔為你收集整理的Cow Relays POJ - 3613的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。