求助!
查看原帖
求助!
625821
2011qiqi楼主2022/7/31 17:33

用的Floyd,样例全过,提交0分,1个WA,剩下全部RE,代码:

#include<bits/stdc++.h>

using namespace std;

int n,a[200][200],p,b[100];
int vis[100];

long long ans=3147483647;

void dfs(int now,int m,long long cnt){
	if(m==0){
		ans=min(ans, cnt+a[now][n]);
	}else{
		for(int i=1;i<=p;i++)if(!vis[i]){
			vis[i]=1;
			dfs(b[i], m-1, cnt+a[now][b[i]]);
			vis[i]=0;
		}
	}
}
int main(){
	char c[100];
    int tot=0;
	while(scanf("%s", c)==1){
		long long k;
		scanf("%d", &n);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				scanf("%d", &a[i][j]);
			}
		}
		scanf("%d", &p);
		scanf("\n");
		for(int i=1;i<=p;i++) scanf("%d", &b[i]);
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(a[i][k]!=0 && a[k][j]!=0) a[i][j]=min(a[i][j], a[i][k]+a[k][j]);
				}
			}
		}		
		dfs(1,p,0);
		printf("样例输出%d\n%lld\n\n", ++tot, ans);
		ans=3147483647;
        memset(vis, 0, sizeof(vis));
	}
	return 0;
}
2022/7/31 17:33
加载中...