DFS最短路径


#include 
using namespace std;
const int INF=99999999;
int n,m;
int v[10000];//用来判断是否走过该点
int dist[10000][10000];  //第i和城市到第j个城市的距离
int minn=INF;
void dfs(int cur,int dis)   //此处的dis是累计的最短距离
{
    if(cur==n)
       {
           minn=min(minn,dis);
           return ;
       }
    if(dis>minn)//说明这个地方是孤立点  不存在通道
        return;
    for(int j=1;j<=n;j++)
    {
        if(dist[cur][j]!=INF&&v[j]==0) //cur到城市j的距离不是无穷
          {
              v[j]=1;
        dfs(j,dis+dist[cur][j]);
        v[j]=0;
          }
    }
    return;
}
int main()
{
    int a,b,c;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) dist[i][i]=0;//自身距离是0 ,任意两孤立点之间是无穷
            else
            {
                dist[i][j]=INF;
            }
        }
    }
     for( int i=1;i<=m;i++)
            {
                cin>>a>>b>>c;
                dist[a][b]=c;//两个城市a b之间的距离是c
            }
    v[1]=1;
    dfs(1,0);
    cout<<minn;
    return 0;
}

相关