問題↓ judge.u-aizu.ac.jp 解説 「各立方体は 0 個，1 個 または 2 個の立方体と重なることがあるが，3 個以上とは重ならない．」という条件から各立方体は鎖状もしくは環状になることがわかる。 任意の二つの立方体が重なるかどうかは少し考えればわかる（…

解法：全探索＋ダイクストラ馬車券を使う順序が重要で、1 全組み合わせのそれぞれについてダイクストラで最短を求めてそのなかで一番小さい値が答え。 通常のダイクストラを拡張して、馬車券を何枚目まで使ったか、という次元を加える。priority_queueに三つ…

解法：ダイクストラ＋少しの考察。 まずダイクストラ法で各町についてショッピングモールまでの最短距離を求める。 次にそれぞれの道について、関数calcで計算する。 関数calcは道の両端の町のショッピングモールまでの最短距離と道の長さからその道の間にあ…

http://abc014.contest.atcoder.jp/tasks/abc014_4完全にmemoで保存用O(N^2) #include <bits/stdc++.h> using namespace std; const int M = 100010; vector<int> G[M]; int root; int n,q; int parent[M]; int depth[M]; void dfs(int v,int p,int d){ parent[v] = p; depth[v] </int></bits/stdc++.h>…

http://poj.org/problem?id=2394解法：ダイクストラやるだけ。JOI予選近いですね・・・ #include <cstdio> #include <queue> #include <vector> using namespace std; int f,p,c,m; const int INF = 100000000; const int MAX_V = 510; struct edge{ int to,cost;}; typedef pair<int,int> P;</int,int></vector></queue></cstdio>…

問題文 http://poj.org/problem?id=3615ワーシャルフロイド法をちょっとだけいじる。 N iostreamを使うとTLEした。 #include <cstdio> using namespace std; const int INF = 100000000; int n,m,t; int d[305][305]; int main(){ for(int i = 0;i <= 303;i++){ for(</cstdio>…