前三道题目 普及-的难度就不说了。

 

最后一道题目难度 普及+~提高-的难度

向复杂了，花了1小时解决题目。

思路就是 floyd+dfs

1 #include 
     
       2 using namespace std; 3 int dis[205][205]; 4 int tot=0x3f3f3f3f,vis[205]; 5 int n,m,r,Start; 6 int R[12]; 7 int x,y,z; 8   9 void floyd(){10     for (int k = 1; k <= n; k++) {11             for (int i = 1; i <= n; i++) {12                 if (i == k) continue;13                 for (int j = 1; j <= n; j++) {14                     if (i == j || k == j) continue;15                     dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);16                 }17             }18         }19         20 }21  22 void dfs(int last,int x,int num){23     if(x>r){24         tot = min(tot,num);25         return;26     }27     for(int i=1;i<=r;i++){28         if(!vis[R[i]]){29             vis[R[i]]=1;30             dfs(R[i],x+1,num+dis[last][R[i]]);31             vis[R[i]]=0;32         }33     }34 }35  36 int main(){37     memset(dis,0x3f3f3f3f,sizeof(dis));38     scanf("%d%d%d",&n,&m,&r);39     for(int i=1;i<=r;i++) scanf("%d",&R[i]);40     for(int i=1;i<=m;i++){41         scanf("%d%d%d",&x,&y,&z);42         dis[x][y]=z;43         dis[y][x]=z;44     }45     floyd();46     for(int i=1;i<=r;i++){47         vis[R[i]]=1;48         dfs(R[i],2,0);49         vis[R[i]]=0;50     }51     printf("%d\n",tot);52     return 0;53 }