很有意思的题= =..... 紧跟zzy大神的步伐A题.... 这里结合离散数学的知识：
离散数学中图的矩阵表示法 用i,j为1表示i到j有一条边,A*A即A^2就是说i-j为2条边的路径种类有多少条。但是这个题的话是运用Floyd的思想，每次更新边使得路径条数+1.多的不说了 不说i我的思想。但是对图论的理解又进了一步！
#include<iostream>
#define MAXEdge 1000005
#define MAXN 1005
using namespace std;int dist[MAXN][MAXN];
struct Edge
{int u,v,price;
}edge[MAXEdge];struct Floyd
{int ans[101][101];
};int N,T,S,E;
int cnt;
Floyd YB;void Matrix2( Floyd &a,Floyd b )
{Floyd K;memset( K.ans,0x6F,sizeof(K.ans) ); int i,j,k;for( k=1;k<=cnt;k++ )for( i=1;i<=cnt;i++ )for( j=1;j<=cnt;j++ )if( K.ans[i][j]>a.ans[i][k]+b.ans[k][j]&&a.ans[i][k]+b.ans[k][j]>0 )K.ans[i][j]=a.ans[i][k]+b.ans[k][j];a=K;
}void MatrixXmult( int k,Floyd &pre )
{Floyd now1=pre;Floyd now2=pre;if( k<=1 ) return ;else if( k%2==0 ){MatrixXmult( k>>1,now1 );Matrix2( now1,now1 );}else if( k%2==1 ){MatrixXmult( k-1,now1 );Matrix2( now1,now2 );}pre=now1;
}int main()
{while( scanf( "%d %d %d %d",&N,&T,&S,&E )!=EOF ){int i,u,v,price;bool inCow[1001];memset( inCow,0,sizeof(inCow) );int hash[1001];memset( hash,0,sizeof(hash) );for( i=1;i<=T;i++ ){scanf( "%d %d %d",&edge[i].price,&edge[i].u,&edge[i].v );inCow[ edge[i].u ]=true;inCow[ edge[i].v ]=true;}cnt=0;for( i=1;i<=1000;i++ ){if( inCow[i] )hash[i]=++cnt;}memset( YB.ans,0x7F,sizeof(YB.ans) );for( i=1;i<=T;i++ ){YB.ans[ hash[ edge[i].u ] ][ hash[ edge[i].v ] ]=edge[i].price;YB.ans[ hash[ edge[i].v ] ][ hash[ edge[i].u ] ]=edge[i].price;}MatrixXmult( N,YB );printf( "%d\n",YB.ans[hash[S]][hash[E]] );}return 0;
}