POJ 3613 Cow Relays 恰好n步的最短路径

?

题目大意：

有T条路，从s到e走n步，求最短路径。

思路：

看了别人的。。。

先看一下Floyd的核心思想: edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
i到j的最短路是i到j的直接路径或者经过k点的间接路径，但是矩阵的更新总是受到上一次更新的影响
如果每次的更新都存进新矩阵，那么edge[i][k]+edge[k][j]是不是表示只经过三个点两条边的路径呢？
min(edge[i][j],edge[i][k]+edge[k][j])就表示只经过三个点两条边的最短路。

?

?

?

 #include
  
   
#include
   
     #include
    
      using namespace std; typedef long long LL; const int MAXN=256; const int INF=0x3fffffff; int num[MAXN<<2]; int n,t,s,e,cnt; struct Matrix { LL data[MAXN][MAXN]; Matrix() { for(int i=0;i
     
      >=1; } } int main() { cnt=0; scanf(%d%d%d%d,&n,&t,&s,&e); int from,to,val; memset(num,-1,sizeof(num)); for(int i=0;i
      
       
?