Prim法(全域最小木) + オマケに植木算。以前やったウォーターデブンのソースと似た感じ。
#include <iostream> #include <set> #include <algorithm> #include <climits> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define MP(a,b) make_pair(a,b) int main(){ int n,m,a,b,c,mi,ret; int info[100][100]; pair<int,int> now; while(cin >> n && n){ cin >> m; ret = 0; rep(i,100)rep(j,100)info[i][j] = INT_MAX; rep(i,m){ scanf("%d,%d,%d\n",&a,&b,&c); info[a][b] = info[b][a] = (c/100)-1; } set<int> remain; for(int i=1;i<n;i++)remain.insert(i); while(!remain.empty()){ now = MP(1<<21,-1); rep(i,n) if(remain.find(i) == remain.end() ) rep(j,n) if(remain.find(j) != remain.end())now = min(now,MP(info[i][j],j)); ret+=now.first; remain.erase(now.second); } cout << ret << endl; } }