城市地图-- 图的深度优先搜素

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int mindis = 9999999 ;
const int MAX = 1000 ;
int n ,m  ;
int book[MAX];
int map[MAX][MAX] ;
void init()
{
  int i ;
  int j ;
  for(i=1;i<=n;i++)
  {
    for(j = 1;j<=n ;j++)
    {
      if(i==j)
      map[i][j] = 0 ;
      else
      map[i][j] = mindis ;
    }
  }
  int a ,b ,c ;
  for(i=1;i<=m;i++)
  {
    cin>>a>>b>>c;
    map[a][b] = c ;

  }

  return ;

}
void dfs(int cur ,int dis)
{
  int i ;
  if(dis>mindis)
  return ;
  if(cur==n)
  {
    if(dis<mindis)
    mindis =dis ; // 更新最小路径;
    return ;
  }

  for(i=1;i<=n;i++)
  {
    if(map[cur][i]!=mindis && book[i]==0)
    {
      book[i] = 1 ;
      dfs(i,dis+map[cur][i]); // 从城市i再出发继续寻找目标;
      book[i] = 0 ; // 之前一步探索完毕后,取消对城市i 的标记

    }

  }
  return ;
}
int main()
{
  int i;
  cin>>n >>m ;
  init();
  book[1] = 1 ; // 标记1号城市已经在路径中了
  dfs(1,0);// 1 表示当前所在的城市编号,0表示当前走过的路程

  cout<<mindis<<endl;

  return 0 ;
}
/*
测试数据:
5 个城市 8 条路线
第 2 到9 行 表示 ai 到 bi 的权值为ci
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3

输出
9

*/