0072 - Carden Lantern
#include <algorithm> #include <cstdio> #include <functional> #include <iostream> #include <queue> #include <utility> #include <vector> using namespace std; #define MAX_N 100 typedef pair<int,int> P_II; vector<P_II> G[MAX_N]; void Prim(int n) { int answer=0; bool used[n]; priority_queue< P_II,vector<P_II>,greater<P_II> > que; fill(used,used+MAX_N,false); que.push( P_II(0,0) ); while ( !que.empty() ) { P_II p_ii=que.top(); que.pop(); int cost=p_ii.first, v=p_ii.second; if ( used[v] ) continue; used[v]=true; answer+=cost; for (int u=0; u<G[v].size(); ++u) que.push( P_II(G[v][u].first,G[v][u].second) ); } cout << answer << endl; } void Slove(int n) { int m, a, b, cost; for (int i=0; i<MAX_N; ++i) G[i].clear(); cin >> m; for (int i=0; i<m; ++ i) { scanf ("%d,%d,%d", &a, &b, &cost); G[a].push_back( P_II(cost/100-1,b ) ); G[b].push_back( P_II(cost/100-1,a ) ); } Prim(n); } int main(void) { int n; while (cin >> n && n) Slove(n); return 0; }
Priority_queueとPrim法使って解いた。
初期化やり忘れてWAしてた。。