Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #define MAXN 1001
- #define INFTY 100000000
- using namespace std;
- struct edge{
- int b, w;
- };
- vector<edge> G[MAXN];
- //vector<edge> G[MAXN];
- //vector<vector<edge> > G;
- //edge G[MAXN][MAXN];
- int visited[MAXN];
- int size[MAXN];
- int parent[MAXN];
- int LOL, r;
- int min(int x, int y){
- return (x > y) ? y : x;
- }
- int stuff(){
- cout << "1000 1\n";
- for( int i = 1; i < 1000; ++i ){
- cout << i << " " << i + 1 << " 1000\n";
- }
- cout << "0 0";
- }
- int go(int curr){
- int ret;
- int sum = 0;
- //++LOL;
- //cout << "deb: go( " << curr << ")\n";
- if( size[curr] == 1 && curr != r ) //jestem lisciem >.<
- return INFTY;
- for( int i = 0; i < size[curr]; ++i ){
- if( G[curr][i].b == parent[curr] ) continue;
- //cout << "list: " << i << " b= " << G[curr][i].b << " w= " << G[curr][i].w << " [curr: " << curr << "]\n";
- parent[G[curr][i].b] = curr;
- ret = go( G[curr][i].b);
- if( ret == INFTY ){
- sum += G[curr][i].w;
- }else{
- sum += min(ret, G[curr][i].w );
- }
- }
- return sum;
- }
- int main(){
- int n, a, b, w;
- edge tmp;
- ios_base::sync_with_stdio(0);
- cin >> n >> r;
- //vector<vector<edge> > G;
- //for(int i = 0; i <= n; ++i) G.push_back( vector<edge>() );
- //G.reserve(n+2);
- while( true ){
- cin >> a >> b;
- if( a == 0 && b == 0 )
- break;
- cin >> w;
- tmp.b = b;
- tmp.w = w;
- //cout << "EDGE " << a << " <-> " << b << " w: " << w << "\n";
- //G[a][size[a]] = tmp;
- G[a].push_back( tmp );
- ++size[a];
- tmp.b = a;
- tmp.w = w;
- //G[b][size[b]] = tmp;
- G[b].push_back( tmp );
- ++size[b];
- }
- cout << go( r);
- //stuff();a.cpp:86:27: error: no match for ‘operator*’ in ‘*G’
- //cout << "\n" << LOL;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement