2018.09.15 hdu1599find the mincost route（floyd求最小环）

传送门

floyd求最小环的板子题目。

就是枚举两个相邻的点求最小环就行了。

代码：

#include<bits/stdc++.h>#define inf 0x3f3f3f3f3f3f#define ll long longusing namespace std;inline ll read(){    ll ans=0;    char ch=getchar();    while(!isdigit(ch))ch=getchar();    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();    return ans;}ll dis[105][105],f[105][105],ans;int n,m;int main(){    while(~scanf("%d%d",&n,&m)){        for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)dis[i][j]=f[i][j]=inf;        for(int i=1;i<=m;++i){            int u=read(),v=read();            ll w=read();            dis[u][v]=dis[v][u]=f[u][v]=f[v][u]=min(f[u][v],w);        }        ans=inf;        for(int k=1;k<=n;++k){            for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)                if(i!=j&&j!=k&&k!=i)ans=min(ans,dis[i][j]+f[i][k]+f[k][j]);            for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);        }        if(ans==inf)puts("It's impossible.");        else printf("%I64d\n",ans);    }    return 0;}