hdu1599 find the mincost route

课件的这一题是放在floyd的后面

以前floyd的代码一直是记下来的

事实上并没有弄清其中的原理

【背代码真的不好

重新理解了一下floyd：

§设 d[ i , j , k ] 是在只允许经过结点1…k 的情况下，i 到 j 的最短路长度，则它有两种情况：

①最短路经过点k，d[i][j][k]=d[i][k][k-1]+d[k][j][k-1]

②最短路不经过点k，d[i][j][k]=d[i][j][k-1]

嗯…也可以按照 0 1 背包的思路去理解它

hdu这一题的意思呢 是求最小环

【自己是真想不到用floyd求最小环

动规的思路真的是特别巧妙

以下题解参考曹文老师课件：

课件后面附有主程序

自己写了一遍+调了一会儿 wa

照着标程抄了一遍 wa

期间ans变成负值

或是各种奇怪的数字

我真的不知道两个inf相加会溢出变成负数

找博客里面的标程

反复修改调试了一上午

中午睡醒了继续

最后将inf的值修改了就好了

徐说最好是赋值为1e9

大概每天都在想问问题但怕打扰他

自己又走很多弯路的那种

找了近乎大半天的bug真的是难过哭

自己写的代码里将f[i][i]赋为0就wa了

曹老师的代码加了这一句就没事

因为毕竟是曹老师吧

也可能我跟oi真的没有缘分…

以下ac代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 101
#define inf 1e9
using namespace std;
template <typename T> void read(T &x){
	x=0;int f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-'0';
	x*=f;
}

int n,m,ans;
int f[maxn][maxn][maxn];

int main(){
	while(cin>>n>>m){
		for(int i=0;i<=n;++i)
			for(int j=1;j<=n;++j)
				for(int k=1;k<=n;++k)
					if(j!=k) f[i][j][k]=inf;
		for(int i=1;i<=m;++i){
			int u,v,w;
			read(u),read(v),read(w);
			f[0][u][v]=min(f[0][u][v],w);//重边判断 
			f[0][v][u]=f[0][u][v];
		}
		int ans=inf;
		for(int k=1;k<=n;++k){
			for(int i=1;i<=n;++i)
				for(int j=1;j<=n;++j)
					f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j]);
			for(int i=1;i<=k-2;++i)
				for(int j=i+1;j<=k-1;++j)
					if(f[0][i][k]<inf&&f[0][j][k]<inf)
						ans=min(ans,f[k-1][i][j]+f[0][i][k]+f[0][k][j]);
		} 
		if(ans<inf) cout<<ans<<endl;
		else cout<<"It's impossible."<<endl;
	}
 	return 0;
}