</pre>题目传送门</p><p></p><p><u>典型的Floyd+最小环的应用，动态规划求解，不懂这个算法请戳<a target=_blank href="http://blog.sina.com.cn/s/blog_476a25110100mag6.html">Floyd+最小环</a></u></p><p></p><p>以下为ac代码</p><p></p><p><pre name="code" class="cpp">#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define inf 1<<28
int n,m,minn;
int maze[110][110];
int dis[110][110];

void Floyd()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<k; i++)
        {
            for(int j=1; j<i; j++)
            {
                minn=min(minn,dis[i][j]+maze[i][k]+maze[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]);
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
               maze[i][j]=inf;
            }
        }
        int a,b,len;
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b>>len;
            maze[a][b]=maze[b][a]=min(maze[a][b],len);
        }
        minn=inf;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[i][j]=maze[i][j];
            }
        }
        Floyd();
        if(minn==inf)
            puts("It's impossible.");
        else
            printf("%d\n",minn);
    }
    return 0;
}