题目链接
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define LL __int64
#define MOD 1000000007
#define INF 0xffffff
int dp[][],g[][],pre[][];
int ans[];
int main()
{
int n,m,minz,i,j,k,sv,ev,w,num,temp;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(pre,-,sizeof(pre));
for(i = ; i <= n; i ++)
{
for(j = ; j <= n; j ++)
dp[i][j] = g[i][j] = INF;
dp[i][i] = g[i][i] = ;
}
for(i = ; i <= m; i ++)
{
scanf("%d%d%d",&sv,&ev,&w);
g[sv][ev] = dp[sv][ev] = min(dp[sv][ev],w);
g[ev][sv] = dp[ev][sv] = min(dp[ev][sv],w);
pre[sv][ev] = ev;
pre[ev][sv] = sv;
}
minz = INF;
for(i = ; i <= n; i ++)//求最小环
{
for(j = ; j <= i-; j ++)
for(k = j+; k <= i-; k ++)
{
if(minz > dp[j][k] + g[j][i] + g[i][k])
{
minz = dp[j][k] + g[j][i] + g[i][k];
num = ;
ans[] = i;
temp = j;
while(temp != -)
{
ans[num++] = temp;
temp = pre[temp][k];
}
}
}
for(j = ; j <= n; j ++)
for(k = ; k <= n; k ++)
{
if(dp[j][k] > dp[j][i] + dp[i][k])
{
dp[j][k] = dp[j][i] + dp[i][k];
pre[j][k] = pre[j][i];
}
}
}
if(minz == INF)
printf("No solution.\n");
else
{
for(i = ;i < num;i ++)
{
if(i == )
printf("%d",ans[i]);
else
printf(" %d",ans[i]);
}
}
printf("\n");
}
return ;
}
