关于#全源最短路#的问题，如何解决？

Question

今天做多源最短路，遇到下面问题：

传送门

图片：

只拿了90分（满分100）
我的代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,d[105][105],p;
long long anss=0x7fffffff; 
bool bo[105],vis[105];
void dfs(int x,int m,long long ss)
{
    if(m>=p)
    {
        anss=min(anss,ss+d[x][n]);
        return;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&bo[i])
            {
                vis[i]=true;
                dfs(i,m+1,ss+d[x][i]);
                vis[i]=false;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
         for(int j=1;j<=n;j++)
         {
             scanf("%d",&d[i][j]);
        }
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(d[i][k]!=0&&d[k][j]!=0)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    scanf("%d",&p);
    for(int i=1;i<=p;i++)
    {
        int x;
        scanf("%d",&x);
        bo[x]=true; 
    }
    vis[1]=true;
    dfs(1,1,0);
    printf("%lld",anss);
} 

Answer 1

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7625819
• 这篇博客你也可以参考下：模拟词法分析的过程，编写一个程序，用于统计文件中单词的总数
• 除此之外, 这篇博客: 【数据结构与算法】八大排序（中）快速排序 快排居然还能这么优化？快排的非递归该如何写？中的 4、🌈最终优化代码（没有加上小区间处理） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• void GetMidIndex(int*a,int begin,int end)
  {
  	int mid=(begin+end)/2;
  	if(a[begin]<a[end])
  	{	
  		if(a[mid]>a[end])
  		return end;
  		else if(a[mid]<a[begin])
  		return begin;
  		else
  		return mid;
  	}
  	else
  	{
  		if(a[mid]>begin)
  		return begin;
  		else if(a[mid]<a[end])
  		return end;
  		else
  		return mid;
  	}
  	//找到了之后和begin交换以下即可作为keyi
  }
  
  int PartSort(int *a,int begin,int end)
  {
  	int prev,cur,key;
  	prev=key=begin;
  	cur=begin+1;
  	int midi=GetMidIndex(a,begin,end);
  	Swap(&a[midi],&a[begin]);
  	while(cur<=end)
  	{
  		if(a[cur]<a[key])
  		{
  			++prev;
  			Swap(&a[cur],&a[prev]);
  		}
  		++cur;
  	}
  	Swap(&a[prev],&a[key]);
  	return prev;
  }
  
  void QuickSort(int *a,int begin,int end)
  {
  	if(begin>=end)
  	return ;
  	int keyi=PartSort(a,begin,end);
  	QuickSort(a,begin,keyi-1);
  	QuickSort(a,keyi+1,end);
  }
  

• 您还可以看一下 刘建萍老师的人工智能系列课程零基础讲解知识点和实例应用线性回归梯度下降逻辑回归课程中的 讲解机器学中会涉及到的有关数学方面的知识储备有哪些小节, 巩固相关知识点