- 首页 > it技术 > >
PTA 7-10 公路村村通 （30 分）
#include using namespace std;
const int inf = 999999;
int n, m;
//N为城镇数目，M为候选道路数目
int g[1000][1000];
//g[][]用来存储城镇之间的距离
int x, y, z;
//初始化时x,y用作一条路径两端的城镇，z用作路径的长度
int cost[1000];
//cost[][]用来作为最短路径的每段长度int prime();
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
#endif
cin >> n >> m;
for(int i = 1;
i <= n;
i++){for(int j = 1;
j <= n;
j++){g[i][j] = g[j][i] = inf;
}
}
while(m--){cin >> x >> y >> z;
g[x][y] = g[y][x] = z;
} for(int i = 1;
i <= n;
i++){cost[i] = g[1][i];
}
cout << prime() << endl;
return 0;
}int prime()
{
int sum = 0;
cost[1] = -1;
int i;
for(i = 1;
i < n;
i++){int minimum = 999999;
int k = -1;
for(int j = 1;
j <= n;
j++){if(cost[j] != -1 && cost[j] < minimum){minimum = cost[j];
k = j;
}}if(k != -1){sum += cost[k];
cost[k] = -1;
for(int j = 1;
j <= n;
j++){if(g[k][j] < cost[j]) cost[j] = g[k][j];
}}
}
for( i = 1;
i <= n;
i++){if(cost[i] != -1) break;
}
if(i <= n) return -1;
else return sum;
}
推荐阅读
