Source Code
Problem: 1258 User: fan1913068672Memory: 204K Time: 16MSLanguage: C++ Result: Accepted Source Code #include"iostream" #include"cstdio" using namespace std; const int INF = 100000+1; int G[101][101]; int visit[101]; struct Edge{ int st; int len; }Edges[101]; int n; int prim(int start){ int sum = 0; for(int i=0;i<n;i++){ Edges[i].st = start; Edges[i].len = INF; } visit[start] = 1; for(int i=0;i<n-1;i++){ for(int j=0;j<n;j++){ int len = G[start][j]; if((len>0&&len<INF)&&!visit[j]&&len<Edges[j].len){ Edges[j].len = len; Edges[j].st = start; } } int Min = INF; int Min_ed; for(int j=0;j<n;j++){ int len = Edges[j].len; if(len<Min&&!visit[j]){ Min = len; Min_ed = j; } } start = Min_ed; visit[start] = 1; sum += Min; } return sum; } int main(){ while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++){ visit[i] = 0; for(int j=0;j<n;j++){ scanf("%d",&G[i][j]); } } printf("%d\n",prim(0)); } return 0; }