静かで孤独な日記

のんびりたまに

AOJ 2237 The Castle

#include<bits/stdc++.h>
using namespace std;

int n,m;
double dp[(1<<16)][17];
double a[20][20];

double memo(int state,int enemy){
	if(enemy==m)return 1;
	if(state==(1<<n)-1)return 0;
	if(dp[state][enemy]>=0)return dp[state][enemy];
	double &res=dp[state][enemy];
	res=0;
	for(int i=0;i<n;i++){
		if(state&(1<<i))continue;
		double now=1,sum=0;
		for(int j=enemy;j<m;j++){
			sum+=now*(1-a[i][j])*memo((state|(1<<i)),j);
			now*=a[i][j];
		}
		sum+=now;
		res=max(res,sum);
	}
	return dp[state][enemy];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout<<fixed;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<(1<<16);i++)
	  for(int j=0;j<17;j++)
	  	dp[i][j]=-1;
	cout<<memo(0,0)<<endl;
	return 0;
}
  • ループでdpやって答えが合わなかったから、メモ化再帰でやりました。
  • stateは死んだら1、生きてたら0です。
  • 最適に行動したいので、どの猫がいつ死んで次にどの猫を戦わせれば良いかを知っておく必要がある。
  • んー、難しいですね。
  • 下のリンクは公式解説スライドです。

AOJ 2585 1 Day Passport

#include<bits/stdc++.h>
using namespace std;

/*
http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2014/Practice/模擬国内予選/講評&openfile=D.pdf
*/

const int inf=1e9;

int main(){
  ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m,h,k;
	while(cin>>n>>m>>h>>k,n){
		vector<tuple<int,int,int,int> > v[101];
		for(int i=0;i<m;i++){
			int a,b,c,d,e;cin>>a>>b>>c>>d>>e;
			a--;b--;e--;
			v[a].push_back(make_tuple(b,c,d,e));
			v[b].push_back(make_tuple(a,c,d,e));
		}
		int s,t;cin>>s>>t;
		s--;t--;
		int p;cin>>p;
		int a[500],b[500];
		for(int i=0;i<p;i++){
			int l,d;cin>>l>>d;
			int now=0;
			for(int j=0;j<l;j++){
				int tmp;cin>>tmp;
				tmp--;
				now|=(1<<tmp);
			}
			a[i]=d;
			b[i]=now;
		}
		int dp[300][300];
		for(int i=0;i<300;i++)for(int j=0;j<300;j++)dp[i][j]=inf;
		dp[0][0]=0;
		for(int i=0;i<p;i++){
			for(int j=0;j<(1<<k);j++){
				dp[i+1][j|b[i]]=min(dp[i+1][j|b[i]],dp[i][j]+a[i]);
				dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
			}
		}
		int ans=inf;
		for(int i=0;i<(1<<k);i++){
			if(dp[p][i]==inf)continue;
			int d[101][25];
			for(int j=0;j<n;j++)for(int k=0;k<=h;k++)d[j][k]=inf;
			d[s][0]=0;
			priority_queue<tuple<int,int,int> > q;
			q.push(make_tuple(0,s,0));
			while(!q.empty()){
				int now=get<1>(q.top());
				int nowcost=-get<0>(q.top());
				int nowh=get<2>(q.top());
				q.pop();
				if(nowcost>d[now][nowh])continue;
				for(int j=0;j<(int)v[now].size();j++){
					int next=get<0>(v[now][j]);
					int next_h=get<2>(v[now][j]);
					int next_cost=get<1>(v[now][j]);
					int cop=get<3>(v[now][j]);
					if(i&(1<<cop))next_cost=0;
					if(nowh+next_h<=h && d[next][nowh+next_h]>d[now][nowh]+next_cost){
						d[next][nowh+next_h]=d[now][nowh]+next_cost;
						q.push(make_tuple(-d[next][nowh+next_h],next,nowh+next_h));
					}
				}
			}
			int res=inf;
			for(int j=0;j<=h;j++)res=min(res,d[t][j]);
			ans=min(res+dp[p][i],ans);
		}
		if(ans==inf)cout<<-1<<endl;
		else cout<<ans<<endl;
	}
}
  • これ、簡単だと思ってやったら1週間どハマりした(最悪)(でも良い経験になった)
  • どこでハマったかというと、dijkstraのところで、最初は各頂点への最短距離を持っておくd[N]を使って実装していて、提出してはWAをしていた。
  • これだと、時間と関係なくその頂点の最短距離を保存してしまうからダメ。
  • ダメな理由は、例えば1日がH時間だとして、ある頂点Vに行く行き方が「H-1時間でコスト100」と「H-3時間でコスト200」の2通りあったとする。そしてVから目的地Tまでは「2時間でコスト100」の一本だけがあったとしよう。
  • 前者の方法だとH-1時間でコスト100の内容しかd[V]に保存されず、これではTまで行くには最低H+1時間かかり答えは-1と出力されてしまう。
  • これは明らかに間違っていて、本来出力されるべき答えは300である。H-3時間でコスト200から2時間でTまで行き到着である。
  • このように、必ずしもコストが最小のものでゴールできるとは限らないのでd[頂点][かかった時間]としてdijkstraをしてあげるべきである。

AOJ 2334 Roads on Towns

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;

//幾何ライブラリ
//ほぼ、https://ei1333.github.io/algorithm/geometry_new.html からパクりました

using Real=double;//問題によってはlong double に変更してください
const Real EPS=1e-8;//問題によって値を変更してください
const Real PI=acos(-1.0);//3.141592653589793238...
inline bool eq(Real a,Real b){return fabs(b-a)<EPS;}//誤差を考慮した等価判定
static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;
typedef complex<Real> Point;//点

//直線
struct Line{
    Point p1,p2;
    Line()= default;
    Line(Point a,Point b):p1(a),p2(b){};
};

//線分
struct Segment:Line{
    Segment()= default;
    Segment(Point a,Point b):Line(a,b){}
};

//点同士の大小比較
namespace std {
    bool operator<(const Point &a, const Point &b) {
        return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
    }
}

//外積
Real cross(const Point& a,const Point& b){
    return a.real()*b.imag()-a.imag()*b.real();
}

//内積
Real dot(const Point& a,const Point& b){
    return a.real()*b.real()+a.imag()*b.imag();
}


int ccw(Point a,Point b,Point c){
    b=b-a;c=c-a;
    if(cross(b,c)>EPS)return COUNTER_CLOCKWISE;//1
    if(cross(b,c)<-EPS)return CLOCKWISE;//-1
    if(dot(b,c)<0)return ONLINE_BACK;//2
    if(norm(b)<norm(c))return ONLINE_FRONT;//-2
    return ON_SEGMENT;//0
}

bool intersect(const Segment& s,const Segment& t){
    return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2)<=0 && ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;
}

//Shortest_Path
//グラフの最短距離を求めるアルゴリズムを3種類持っているクラスです
class shortest_path{
public:
    
    //dijkstra法とBellman_Ford法を使うときは、このコンストラクタを使ってください
    explicit shortest_path(int n):vertex(n),INF((double)1e9){
        v1.resize(static_cast<unsigned long>(vertex));
    }
    
    //Warshall_Floyd法を使うときは、こちらのコンストラクタを使ってください
    shortest_path(int n,double inf):vertex(n),INF(inf){
        v2.resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++)v2[i].resize(static_cast<unsigned long>(vertex));
        for(int i=0;i<vertex;i++){
            for(int j=0;j<vertex;j++){
                v2[i][j]=INF;
            }
        }
        for(int i=0;i<vertex;i++)v2[i][i]=0;
    }
    
    //dijkstra法とBellman_Ford法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge(int from,int to,double cost){
        v1[from].push_back({to,cost});
    }
    
    //Warshall_Floyd法専用のadd_edge(int from,int to,ll cost)です
    //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost)
    void add_edge_(int from,int to,ll cost){//warshall_floyd
        v2[from][to]=cost;
    }
    
    //Dijkstra法です
    //各頂点への距離が格納されたvector<ll>が求まります
    //負のコストの辺がある場合は使えません
    //start地点の頂点番号を引数に入れてください
    vector<double> dijkstra(unsigned int start){
        vector<double> d(static_cast<unsigned long>(vertex),INF);
        priority_queue<pair<double,int> > q;
        d[start]=0;
        q.push({0,start});
        while(!q.empty()){
            int now=q.top().se;
            double now_cost=-q.top().fi;
            q.pop();
            if(d[now]<now_cost)continue;
            for (auto &i : v1[now]) {
                if(d[i.fi]>now_cost+ i.se){
                    d[i.fi]=now_cost+ i.se;
                    q.push({-d[i.fi], i.fi});
                }
            }
        }
        return d;
    }
    
    //Warshall_Floyd法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    tuple<vector<vector<ll> >,bool> warshall_floyd(){
        for(int k=0;k<vertex;k++){
            for(int i=0;i<vertex;i++){
                if(v2[i][k]==INF)continue;
                for(int j=0;j<vertex;j++){
                    if(v2[k][j]==INF)continue;
                    v2[i][j]=min(v2[i][j],v2[i][k]+v2[k][j]);
                }
            }
        }
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            if(v2[i][i]<0)is_negative_cycle=true;
        }
        return make_tuple(v2,is_negative_cycle);
    }

    //Bellman_Ford法です
    //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます
    //閉路があるとき、返り値はtrueです
    //start地点の頂点番号を引数に入れてください
    tuple<vector<ll>,bool> bellman_ford(int start){
        vector<ll> d(static_cast<unsigned long>(vertex),INF);
        d[start]=0;
        bool is_negative_cycle=false;
        for(int i=0;i<vertex;i++){
            bool update= false;
            for(int j=0;j<vertex;j++){
                if(d[j]==INF)continue;
                for(int k=0;k<(int)v1[j].size();k++){
                    if(d[v1[j][k].fi]>d[j]+v1[j][k].se){
                        d[v1[j][k].fi]=d[j]+v1[j][k].se;
                        update= true;
                    }
                }
            }
            if(i==vertex-1 && update)is_negative_cycle=true;
            else if(!update)break;
        }
        return make_tuple(d,is_negative_cycle);
    }
private:
    double INF;
    int vertex;
    vector<vector<pair<int,double> > > v1;
    vector<vector<ll> > v2;
};

int na,nb;
double xa[1001],ya[1001],xb[1001],yb[1001];

int main(){
  int na,nb;
  cin>>na>>nb;
  for(int i=0;i<na;i++){
    cin>>xa[i]>>ya[i];
  }
  for(int i=0;i<nb;i++){
    cin>>xb[i]>>yb[i];
  }
  Point tmp(xb[0],yb[0]);
  Point tmp2(xb[1],yb[1]);
  Segment s1(tmp,tmp2);
  shortest_path sp1(na);
  //cout<<1<<endl;
  for(int i=0;i<na;i++){
    for(int j=i+1;j<na;j++){
      Point a(xa[i],ya[i]);
      Point b(xa[j],ya[j]);
      Segment aa(a,b);
      //cout<<aa.p1<<" "<<aa.p2<<endl;
      if(!intersect(s1,aa)){
        //cout<<i<<"--"<<j<<endl;
        sp1.add_edge(i,j,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j])));
        sp1.add_edge(j,i,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j])));
      }
    }
  }
  vector<double> di1=sp1.dijkstra(0);
  double ans;
  if(di1[1]!=1e9){
    ans=di1[1]+getDistance(tmp,tmp2);
  }else{
    ans=inf;
  }
  Point tmp3(xa[0],ya[0]);
  Point tmp4(xa[1],ya[1]);
  Segment s2(tmp3,tmp4);
  shortest_path sp2(nb);
  //cout<<2<<endl;
  for(int i=0;i<nb;i++){
    for(int j=i+1;j<nb;j++){
      Point a(xb[i],yb[i]);
      Point b(xb[j],yb[j]);
      Segment aa(a,b);
      if(!intersect(s2,aa)){
        //cout<<i<<"--"<<j<<endl;
        sp2.add_edge(i,j,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j])));
        sp2.add_edge(j,i,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j])));
      }
    }
  }
  vector<double> di2=sp2.dijkstra(0);
  if(di2[1]!=inf){
    ans=min(ans,di2[1]+getDistance(tmp3,tmp4));
  }else{
    ans=min(ans,inf);
  }
  if(ans!=inf){
    printf("%.12f\n",ans);
  }else{
    cout<<-1<<endl;
  }
  return 0;
}
  • 街の数が1000くらいだからO(n^2)解があるだろうなんて考えたら簡単に思いついた。
  • 交差判定して交差してなかったら変を追加。
  • 変を追加したら0から1への最短距離求めるためにdijkstraやるだけ。

AOJ 2511 Sinking islands

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;

//union_find
//_n mast be unsigned int
//BEGIN CUT HERE
class union_find{
public:
    explicit union_find(int _n):n(_n){
        par.resize(static_cast<unsigned long>(_n));
        rank.resize(static_cast<unsigned long>(_n));
        sizes.resize(static_cast<unsigned long>(_n));
        for(int i=0;i<_n;i++){
            par[i]=i;
            rank[i]=0;
            sizes[i]=1;
        }
    }
    
    //親ノードを見つけます
    int find(int a){
        if(par[a]==a)return a;
        return par[a]=find(par[a]);
    }
    
    //aとbが同じグループかの判定
    bool same(int a,int b){
        return find(a)==find(b);
    }
    
    //aとbを同じグループにします
    void unite(int a,int b){
        link(find(a),find(b));
    }
    
    //aが属するグループの要素数を求めます
    int size(int a){
        return sizes[find(a)];
    }
    
    //全体がどのグループに属しているかがわかります
    void view(){
        for(int i=0;i<n;i++){
            cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":",");
        }
        for(int i=0;i<n;i++){
            cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":",");
        }
        cout<<endl;
    }

    void init(){
      for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
        sizes[i]=1;
      }
    }

private:
    void link(int a,int b){
        if(same(a,b))return;
        if(rank[a]>rank[b]){
            par[b]=a;
            sizes[a]+=sizes[b];
            sizes[b]=0;
        }else{
            par[a]=b;
            if(rank[a]==rank[b])rank[b]++;
            sizes[b]+=sizes[a];
            sizes[a]=0;
        }
    }
    int n;
    vector<int> par;
    vector<int> rank;
    vector<int> sizes;
};

int main(){
  int n,m;
  while(cin>>n>>m,n){
    vector<pair<int,int> > h;
    for(int i=0;i<n;i++){
      int a;cin>>a;
      h.push_back({a,i});
    }
    union_find tmp(n);
    vector<pair<pair<int,int>,int> > v;
    for(int i=0;i<m;i++){
      int a,b,c;cin>>a>>b>>c;
      a--;b--;
      tmp.unite(a,b);
      v.push_back(make_pair(make_pair(c,a),b));
    }
    if(tmp.size(0)!=n){
      cout<<0<<endl;
      continue;
    }
    sort(h.begin(),h.end());
    reverse(h.begin(),h.end());
    sort(v.begin(),v.end());
    union_find uf(n);
    ll ans=0;
    bool ok[201];
    int cont=0;
    for(int i=0;i<n;i++)ok[i]=0;
    for(int i=0;i<n;i++){
      ok[h[i].se]=1;
      if(i==n-1 || h[i].fi!=h[i+1].fi){
        for(int j=0;j<m;j++){
          int nowa=v[j].fi.se;
          int nowb=v[j].se;
          if(ok[nowa] && ok[nowb] && !uf.same(nowa,nowb)){
            ans+=v[j].fi.fi;
            cont++;
            uf.unite(nowa,nowb);
          }
        }
        if(cont!=i){
          uf.init();
          cont=0;
          ans=0;
        }
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}
  • 日本語が難しかった。。
  • こういう問題に当たりたくないなぁ。。

AOJ 2510 Twin book report

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
bool dp[1001][1001];

int main(){
  int n;
  while(cin>>n,n){
    vector<pair<int,int> > v;
    int sum=0,maxe=0;
    int sumw=0;
    int maxw=0;
    vector<int> vv;
    for(int i=0;i<n;i++){
      int a,b;cin>>a>>b;
      v.push_back({a,b});
      vv.push_back(b);
      sum+=a;
      if(maxe<a){
        maxe=a;
        maxw=i;
      }
      sumw+=b;
    }
    if(maxe<=sum-maxe){
      cout<<sum+sumw<<endl;
    }else{
      int ans=maxe*2+v[maxw].se;
      int nokori=maxe-(sum-maxe);
      vv.erase(vv.begin()+maxw);
      sort(vv.begin(),vv.end());
      int vvsum=0;
      for(int i=0;i<(int)vv.size();i++)vvsum+=vv[i];
      for(int i=0;i<=(int)vv.size();i++)for(int j=0;j<=nokori;j++)dp[i][j]=0;
      dp[0][0]=1;
      for(int i=0;i<(int)vv.size();i++){
        for(int j=0;j<=nokori;j++){
          if(dp[i][j]==0)continue;
          if(j+vv[i]<=nokori){
            dp[i+1][j+vv[i]]=1;
          }
          dp[i+1][j]=1;
        }
      }
      for(int i=nokori;i>=0;i--){
        if(dp[vv.size()][i]){
          cout<<ans+vvsum-i<<endl;
          break;
        }
      }
    }
  }
  return 0;
}
  • とりあえず本を早く全部読み終わりたい。
  • 本当は待たずに全部の本読みたいけど、一つだけめちゃめちゃ読むのに時間がかかる本があるとそうはいかない。
  • そんな場合は待ち時間に感想文書けば良い。
  • 待ち時間をどんなふうに使うのが一番かはdpしてあげるのが一番簡単。

AOJ 2333 My friends are small

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
const ll MOD=(ll)1e9+7;
const int inf=(ll)1e9;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};

int n,w;
int a[211];
int sum[202];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n>>w;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  a[n]=inf;
  n++;
  sort(a,a+n);
  ll ans=0;
  for(int i=0;i<n+1;i++){
    int sum=0;
    for(int j=0;j<i;j++){
      sum+=a[j];
    }
    int nokori=w-sum;
    if(nokori<0)continue;
    //show(nokori);
    int minw=a[i];
    //show(minw);
    ll dp[2][10001];
    for(int j=0;j<2;j++)for(int k=0;k<=w;k++)dp[j][k]=0;
    dp[(i+1)&1][0]=1;
    for(int j=i+1;j<n;j++){
      for(int k=0;k<=w;k++){
        dp[(j+1)&1][k]=0;
      }
      for(int k=0;k<=w;k++){
        if(dp[j&1][k]==0)continue;
        if(k+a[j]<=nokori){
          dp[(j+1)&1][k+a[j]]=(dp[(j+1)&1][k+a[j]]+dp[j&1][k])%MOD;
        }
        dp[(j+1)&1][k]=(dp[(j+1)&1][k]+dp[j&1][k])%MOD;
      }
      /*for(int k=0;k<=w;k++){
        cout<<dp[j&1][k]<<" ";
      }
      cout<<endl;*/
    }
    for(int j=0;j<=nokori;j++){
      if(nokori-j<minw)ans=(ans+dp[n&1][j])%MOD;
    }
  }
  cout<<ans<<endl;
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}
  • 数え上げはもれなくダブりなくを意識したい。
  • 今回はソートして初めて鞄に入れられなかった小人で場合分けをする。これはもれなくダブりのない場合わけである。
  • ソートをする理由は、ソートをせずにナップザックのようなことをすると、もう鞄の中にどんな小人も入る事ができないかどうかの判定ができないからである。

AOJ 1196 Bridge Removal

#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
const int inf=(int)1e9;

vector<vector<pair<int,int> > > v;
bool past[801];
bool leaf[801];

void dfs(int now){
  bool flag=1;
  for(int i=0;i<(int)v[now].size();i++){
    if(past[v[now][i].fi])continue;
    flag=0;
    past[v[now][i].fi]=1;
    dfs(v[now][i].fi);
  }
  if(flag)leaf[now]=1;
}

int bfs(int s){
  int d[801];
  for(int i=0;i<801;i++){
    d[i]=0;
  }
  queue<pair<int,int> > q;
  q.push({s,0});
  bool p[801];
  for(int i=0;i<801;i++)p[i]=0;
  p[s]=1;
  while(!q.empty()){
    int now=q.front().fi;
    int nowcost=q.front().se;
    q.pop();
    for(int i=0;i<(int)v[now].size();i++){
      if(leaf[v[now][i].fi])continue;
      if(p[v[now][i].fi])continue;
      p[v[now][i].fi]=1;
      d[v[now][i].fi]=v[now][i].se+nowcost;
      q.push({v[now][i].fi,v[now][i].se+nowcost});
    }
  }
  int res=0;
  for(int i=0;i<801;i++){
    res=max(res,d[i]);
  }
  return res;
}

int main(){
  int n;
  while(cin>>n,n){
    v.resize(n);
    for(int i=0;i<n;i++)v.resize(0);
    for(int i=0;i<n;i++){
      past[i]=0;
      leaf[i]=0;
    }
    int tmp[801];
    for(int i=0;i<n-1;i++){
      cin>>tmp[i];tmp[i]--;
    }
    ll ans=0;
    for(int i=0;i<n-1;i++){
      int cost;cin>>cost;
      ans+=cost*3;
      v[i+1].push_back({tmp[i],cost});
      v[tmp[i]].push_back({i+1,cost});
    }
    past[0]=1;
    dfs(0);
    for(int i=0;i<n;i++){
      past[i]=0;
    }
    for(int i=0;i<n;i++){
      if(leaf[i]){
        past[i]=1;
        dfs(i);
        break;
      }
    }
    for(int i=0;i<n;i++){
      if(leaf[i])ans-=2*v[i][0].se;
    }
    ll ans2=ans;
    //show(ans);
    for(int i=0;i<n;i++){
      if(leaf[i])continue;
      int maxedge=bfs(i);
      ans2=min(ans2,ans-maxedge);
      //show(maxedge);
    }
    cout<<ans2<<endl;
  }
  return 0;
}
  • あまりいい方法が考えられず、解けなかった
  • どんな場所は何回通るのかをしっかり意識して考えたい。