この問題はDFSにより解くことができます。

現在いる街、すでに行ったことのある街の集合、今までに通った道の長さの合計を保持しながら、まだ行ったことのない街へ移動するDFSをします。

計算量は \(O(N N!)\) であり、十分高速に動作します。

なお競技プログラミングにおいては、実装の簡略化などの理由で、持つべき状態をDFSの引数として渡すかわりにグローバル変数を更新するような実装がしばしばなされます。

実装例(Python)

N,M=map(int,input().split())
E=[[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
  a,b,c=map(int,input().split())
  E[a][b]=c
  E[b][a]=c

ans=0
used=[False]*(N+1)

def dfs(v,s):
  global ans
  used[v]=True
  if s>ans: ans=s
  for i in range(1,N+1):
    if not used[i] and E[v][i]:
      dfs(i,s+E[v][i])
  used[v]=False

for i in range(1,N+1):
  dfs(i,0)

print(ans)

実装例(C)

#include<stdio.h>
#define max(p,q)((p)>(q)?(p):(q))

int n,m;
int e[11][11];
int used[11];
int ans;
void dfs(int v,int sum){
	used[v]=1;
	ans=max(ans,sum);
	for(int i=1;i<=n;i++)if(!used[i]&&e[v][i])dfs(i,sum+e[v][i]);
	used[v]=0;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		e[a][b]=e[b][a]=c;
	}
	for(int i=1;i<=n;i++)dfs(i,0);
	printf("%d\n",ans);
}