首页 > 代码库 > POJ 3613 Cow Relays 恰好n步的最短路径
POJ 3613 Cow Relays 恰好n步的最短路径
http://poj.org/problem?id=3613
题目大意:
有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<cstdio> #include<cstring> #include<algorithm> 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<MAXN;i++) for(int j=0;j<MAXN;j++) data[i][j]=INF; } Matrix & operator = (const Matrix &x ) { for(int i=0;i<cnt;i++) for(int j=0;j<cnt;j++) data[i][j]=x.data[i][j]; return *this; } //这里不返回引用出错。。。我记得C++不是不建议返回局部变量的引用么? Matrix& operator * (const Matrix & x) { Matrix res; for(int k=0;k<cnt;k++) for(int i=0;i<cnt;i++) for(int j=0;j<cnt;j++) res.data[i][j]=min(res.data[i][j],data[i][k]+x.data[k][j]); return res; } }a,b; void mypow() { for(int i=0;i<cnt;i++) b.data[i][i]=0; while(n) { if(n&1) b=b*a; a=a*a; n>>=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<t;i++) { scanf("%d%d%d",&val,&from,&to); if(num[from]==-1) num[from]=cnt++; if(num[to]==-1) num[to]=cnt++; from=num[from]; to=num[to]; a.data[from][to]=a.data[to][from]=val; } mypow(); printf("%d\n",b.data[ num[s] ][ num[e] ]); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。