首页 > 代码库 > POJ 3613

POJ 3613

2024-07-20 19:02:51   218人阅读

可以利用DP的思想来做，不过是在DP时加上了矩阵乘法的思想而已，但乘法不是真的乘法，而是mp[a][i]+mp[i][b]<mp[a][b]则更新，其实更像FLOYD。

但这是符合乘法的格式的。

我们可以利用快速幂的做法来降低复杂度，同时把那些点离散化一下，因为T才100，最多是200多个点而已。

仅有此还不够，我觉得这道题更重要的是一个初始化的问题。

这题的数据可能有回到原点的数据，那么，若I->I=0的话，则会一直不动，所以要初始化到I->I=INF;

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int inf=0x3f3f3f3f;const int Maxn=220;int mark[1010];struct Matrax {	int m[Maxn][Maxn];};Matrax a;int counted=0;Matrax multi(Matrax a,Matrax b){	Matrax c;	for(int i=0;i<counted;i++){		for(int j=0;j<counted;j++){			c.m[i][j]=inf;			for(int k=0;k<counted;k++)			c.m[i][j]=min(c.m[i][j],a.m[i][k]+b.m[k][j]);		}	}	return c;}Matrax Powerg(int k){	bool flag=false;	Matrax ans,p=a;	while(k){		if(k&1){			if(!flag){				ans=p;				flag=true;			}			else {				ans=multi(ans,p);			}		}		k>>=1;		p=multi(p,p);	}	return ans;}int main(){	int n,t,s,e,l,u,v,uu,vv;	while(scanf("%d%d%d%d",&n,&t,&s,&e)!=EOF){		counted=0;		memset(mark,-1,sizeof(mark));		for(int i=0;i<Maxn;i++){			for(int j=0;j<Maxn;j++){				a.m[i][j]=inf;			}		}		for(int i=0;i<t;i++){			scanf("%d%d%d",&l,&uu,&vv);			if(mark[uu]==-1)			mark[uu]=counted++;			if(mark[vv]==-1)			mark[vv]=counted++;			u=mark[uu]; v=mark[vv];			a.m[u][v]=a.m[v][u]=l;		}		Matrax ans=Powerg(n);		s=mark[s]; e=mark[e];		printf("%d\n",ans.m[s][e]);	}	return 0;}

　　

POJ 3613


联系
我们