language: default agri-net
description farmer john has been elected mayor of his town! one of his campaign promises was to bring internet connectivity to all farms in the area. he needs your help, of course. input the input includes several cases. for each case, the first line contains the number of farms, n (3 <= n=””> <= 100).=”” the=”” following=”” lines=”” contain=”” the=”” n=”” x=”” n=”” conectivity=”” matrix,=”” where=”” each=”” element=”” shows=”” the=”” distance=”” from=”” on=”” farm=”” to=”” another.=”” logically,=”” they=”” are=”” n=”” lines=”” of=”” n=”” space-separated=”” integers.=”” physically,=”” they=”” are=”” limited=”” in=”” length=”” to=”” 80=”” characters,=”” so=”” some=”” lines=”” continue=”” onto=”” others.=”” of=”” course,=”” the=”” diagonal=”” will=”” be=”” 0,=”” since=”” the=”” distance=”” from=”” farm=”” i=”” to=”” itself=”” is=”” not=”” interesting=”” for=”” this=”” problem.=””> output for each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms. sample input 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 sample output 28 source usaco 102 |
模板题，直接套模板。。。
代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment (linker,"/stack:102400000,102400000")
#define maxn 105
#define maxn 2005
#define mod 1000000009
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int n;
int mp[maxn][maxn],visit[maxn],dist[maxn];
void prim()
{
int i,j,mi,now;
memset(visit,0,sizeof(visit));
memset(dist,inf,sizeof(dist));
for (i=0;imp[now][j])
dist[j]=mp[now][j];
}
int ans=0;
for (i=0;i
