我也是醉了， 无限WA 。
注意一下使用邻接矩阵时循环语句的不同处。
1 for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) map[i][j]=map[j][i]=(i==j?0:INF) 2 3 和普通写法区别。
#include#include #include #include #define M 601 #define N 1000001using namespace std;const int INF = 0x3f3f3f3f;int sieve[N*2], dis[M], vis[M], Rode[M], map[M][M];int n;int Min(int a, int b){ if(a < b) return a; else return b;}void Is_Prime(){ memset(sieve, 0, sizeof(sieve)); sieve[0] = sieve[1] = 1; for(int i = 2; i < N*2; i++) { if(!sieve[i]) for(int j = 2*i; j < N*2; j += i) sieve[j] = 1; }}void Prime(){ int sum = 0; memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) dis[i] = map[1][i]; vis[1] = 1; for(int i = 1; i < n; i++) { int temp = 1, min = INF; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] < min) { temp = j; min = dis[j]; } } if(min == INF) { printf("-1\n"); return; } vis[temp] = 1; sum += min; for(int j = 1; j <= n; j++) if(!vis[j] && dis[j] > map[temp][j]) dis[j] = map[temp][j]; } printf("%d\n", sum);}int main(){ int T; scanf("%d", &T); Is_Prime(); while(T--) { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &Rode[i]); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) map[i][j] = (i==j?0:INF); for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) if(!sieve[Rode[i]] || !sieve[Rode[j]] || !sieve[Rode[i] + Rode[j]]) map[i][j] = map[j][i] = Min(Min(Rode[i], Rode[j]), abs(Rode[i]-Rode[j])); Prime(); } return 0; }