ABC 006
A問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N; cin >> N; cout << (N%3 == 0 ? "YES" : "NO") << endl; }
Submission #1025003 - AtCoder Beginner Contest 006 | AtCoder
B問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int a[1000010]; int main(void) { int n; cin >> n; a[1] = a[2] = 0; a[3] = 1; FOR(i, 4, n+1) { a[i] = (a[i-1] + a[i-2] + a[i-3]) % 10007; } cout << a[n] << endl; }
Submission #1025009 - AtCoder Beginner Contest 006 | AtCoder
C問題
全てのb
に対して解が存在するか調べる。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N, M; cin >> N >> M; int a, b, c; REP(b, N+1) { int t = M - 3*b; if(t % 2 != 0) continue; c = t/2 - (N-b); a = (N-b) - c; if(a >= 0 && c >= 0) { printf("%d %d %d\n", a, b, c); return 0; } } a = b = c = -1; printf("%d %d %d\n", a, b, c); }
D問題
最長増加部分列問題 (Longest Increasing Subsequence) という典型問題らしい。
k
枚抜いたらソート済みになる最小のk
が求まれば、k
枚を適切な位置に挿入することで全てソート済みの列が作れるからk
が答えになる。- 「今まで見たカードまでで作れる長さ
i
のソート済み部分列の最後の数字の最小値」を格納するdp[i]
を用意しておいてカードを前から見て埋めていく。 - カード
c
を見ているとき、「dp[i-1] < c < dp[i+1]
を満たす最小のi
」に埋めるので二分探索で行う - 埋まっている数の最大値が最小数のカードを抜いた後の残り枚数なので、
N
から最大値を引くと答えになる
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N; cin >> N; vector<int>c(N); REP(i, N) cin >> c[i]; vector<int> dp(N+1, 1e9); dp[0] = -1e9; REP(i, N) { int k = c[i]; int l = 0, r = N+1; while(l < r) { int m = (l + r) / 2; if(k < dp[m]) r = m; else l = m+1; } dp[l] = k; } int ans = 0; REP(i, N+1) { if(dp[i] != 1e9) ans = i; } cout << N-ans << endl; }
Submission #1025896 - AtCoder Beginner Contest 006 | AtCoder
ABC 004
A問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N; cin >> N; cout << 2*N << endl; }
Submission #1024943 - AtCoder Beginner Contest 004 | AtCoder
B問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) typedef long long int ll; using namespace std; int main(void) { char c[4][4]; REP(i, 4) REP(j, 4) cin >> c[i][j]; for(int i=3; i>=0; --i) { for(int j=3; j>0; --j) cout << c[i][j] << " "; cout << c[i][0] << endl; } }
Submission #1024944 - AtCoder Beginner Contest 004 | AtCoder
C問題
観察すると30回ごとに同じパターンになることからN
を30で割った余りを求めてからシミュレーション
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) typedef long long int ll; using namespace std; int main(void) { int N; cin >> N; int c[6]; N %= 30; REP(i, 6) c[i] = i+1; REP(i, N) { swap(c[i%5], c[i%5+1]); } REP(i, 6) cout << c[i]; cout << endl; }
Submission #1024949 - AtCoder Beginner Contest 004 | AtCoder
D問題
dp[pos][remain]
を「0からposまでの箱を使ってマーブルを配置したときに必要な最小の移動数」として動的計画法を行う(ただしposは-400を0とするようにずらしてある)
- 初期化は
dp[i][R+G+B]=0
、その他は大きい数。 - 漸化式は
dp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j))
。(コメントの指摘を受けて修正しました) cost(i, j)
はj
個残っているときにi
番目の箱に入れるための最小の移動数を表す。左から順に入れているので、残りの数によってどの色を入れるのが移動数最小になるのかは一意に定まり、その色の箱の位置とposの差の絶対値が移動量になる。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int R, G, B; int dp[1000][1000]; // dp[pos][remain] = number of move int cost(int pos, int remain) { if(remain >= G+B) return abs(400-pos); else if(remain >= B) return abs(500-pos); else return abs(600-pos); } int main(void) { cin >> R >> G >> B; int total = R + G + B; REP(i, 1000) REP(j, 1000) dp[i][j] = 1e9; REP(i, 1000) dp[i][total] = 0; FOR(i, 1, 1000) { REP(j, total) { dp[i][j] = min(dp[i-1][j], dp[i-1][j+1] + cost(i, j)); } } int ans = 1e9; REP(i, 1000) { ans = min(ans, dp[i][0]); } cout << ans << endl; }
Submission #1024931 - AtCoder Beginner Contest 004 | AtCoder
ABC 005
A問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int x, y; cin >> x >> y; cout << y / x << endl; }
Submission #1024248 - AtCoder Beginner Contest 005 | AtCoder
B問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N; cin >> N; vector<int> T(N); REP(i, N) cin >> T[i]; sort(T.begin(), T.end()); cout << T[0] << endl; }
Submission #1024251 - AtCoder Beginner Contest 005 | AtCoder
C問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int T, N, M; cin >> T >> N; vector<int> A(N); REP(i, N) cin >> A[i]; cin >> M; vector<int> B(M); REP(i, M) cin >> B[i]; bool ok = true; if(M > N) ok = false; int idx = 0; REP(i, M) { bool serve = false; while(idx < N && A[idx] < B[i] - T) idx++; if(A[idx] >= B[i] - T && A[idx] <= B[i]) { idx++; } else { ok = false; } } cout << (ok ? "yes" : "no") << endl; }
Submission #1024261 - AtCoder Beginner Contest 005 | AtCoder
D問題
- 左上
(0, 0)
右下(i, j)
の長方形のおいしさの和をacc[i][j]
に入れる。 (x, y, w, h)
を指定したらその長方形のおいしさの和を返す関数がarea
。- 全ての高さ・幅の長方形に対して最大のおいしさを求める。
- 各たこ焼き数以下で達成できる最大のおいしさを求める。
- 以上の準備をすれば、各店員の焼けるたこ焼き数に対する最大のおいしさがで求まる。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int D[55][55]; int acc[55][55]; int P[2501]; int memo[2501]; int area(int x, int y, int w, int h) { return acc[x+w][y+h] - acc[x+w][y] - acc[x][y+h] + acc[x][y]; } int main(void) { int N, Q; cin >> N; REP(i, N) REP(j, N) cin >> D[i][j]; cin >> Q; REP(i, Q) cin >> P[i]; REP(j, N+1) acc[0][j] = 0; FOR(i, 1, N+1) { int row = 0; acc[i][0] = 0; FOR(j, 1, N+1) { row += D[i-1][j-1]; acc[i][j] = acc[i-1][j] + row; } } REP(i, 2501) memo[i] = 0; REP(w, N+1) { REP(h, N+1) { REP(x, N-w+1) { REP(y, N-h+1) { memo[w*h] = max(memo[w*h], area(x, y, w, h)); } } } } FOR(i, 1, 2501) memo[i] = max(memo[i], memo[i-1]); REP(i, Q) cout << memo[P[i]] << endl; }
Submission #1025052 - AtCoder Beginner Contest 005 | AtCoder
ABC 003
A問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N; cin >> N; double s; REP(i, N) { s += 10000*double(i+1)/N; } printf("%.10f\n", s); }
Submission #1024144 - AtCoder Beginner Contest 003 | AtCoder
B問題
"string"[i]
というテクニックを学んだ
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { string S, T; cin >> S >> T; bool win = true; map<char, bool> ok; REP(i, 7) ok["atcoder"[i]] = true; REP(i, S.size()) { if(S[i] != T[i]) { if(S[i] == '@' && ok[T[i]]) continue; if(T[i] == '@' && ok[S[i]]) continue; win = false; } } if(win) cout << "You can win" << endl; else cout << "You will lose" << endl; }
Submission #1024159 - AtCoder Beginner Contest 003 | AtCoder
C問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N, K; cin >> N >> K; vector<int> R(N); REP(i, N) { cin >> R[i]; } sort(R.begin(), R.end()); double ans = 0; FOR(i, N-K, N) { ans = (ans + R[i]) / 2.0; } printf("%.10f\n", ans); }
Submission #1024161 - AtCoder Beginner Contest 003 | AtCoder
D問題
100点解法。nCrをパスカルの三角形を使って求める。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; const ll mod = 1000000007; vector<vector<int> > C(1000, vector<int>(1000, -1)); ll combination(int n, int r) { if(r == 0 || r == n) return 1; if(C[n][r] != -1) return C[n][r]; return (C[n][r] = (combination(n-1, r-1)+combination(n-1, r))%mod); } int main(void) { int R, C, X, Y, D, L; cin >> R >> C >> X >> Y >> D >> L; cout << ((R-X+1) * (C-Y+1) * combination(D+L, D)) % mod << endl; }
101点解法 Submission #740595 - AtCoder Beginner Contest 003 | AtCoderを見た
上下左右の壁にくっついているパターンの数を、包除原理を用いて上下左右にくっついていないパターンを取り除くことで求める。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; const ll mod = 1e9+7; int R, C, X, Y, D, L; vector<vector<int> > memo(1000, vector<int>(1000, -1)); ll nCr(int n, int r) { if(n < 0 || r < 0 || n < r) return 0; if(r == 0 || r == n) return 1; if(memo[n][r] != -1) return memo[n][r]; return (memo[n][r] = (nCr(n-1, r-1) + nCr(n-1, r))%mod); } int main(void) { cin >> R >> C >> X >> Y >> D >> L; const int N = D + L; if(X*Y == N) { cout << (C-Y+1)*(R-X+1) * nCr(N, L) % mod << endl; } else { ll t = ( ( nCr(X*Y, N) - ( 2 * (nCr((X-1)*Y, N) + nCr(X*(Y-1), N)) ) + ( nCr((X-2)*Y, N) + nCr(X*(Y-2), N) + 4 * nCr((X-1)*(Y-1), N) ) - ( 2 * (nCr((X-2)*(Y-1), N) + nCr((X-1)*(Y-2), N)) ) + ( nCr((X-2)*(Y-2), N) ) ) * nCr(N, L) % mod * (C-Y+1) % mod * (R-X+1) ) % mod; while(t < 0) t += mod; cout << t << endl; } }
ABC 002
A問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int a, b; cin >> a >> b; cout << max(a, b) << endl; }
Submission #1024114 - AtCoder Beginner Contest 002 | AtCoder
B問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { string W; cin >> W; REP(i, W.size()) { if(W[i] != 'a' && W[i] != 'i' && W[i] != 'u' && W[i] != 'e' && W[i] != 'o') { cout << W[i]; } } cout << endl; }
Submission #1024115 - AtCoder Beginner Contest 002 | AtCoder
C問題
ヘロンの公式
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int x[3], y[3]; REP(i, 3) cin >> x[i] >> y[i]; double a = sqrt(pow(x[0] - x[1], 2.0) + pow(y[0] - y[1], 2.0)); double b = sqrt(pow(x[1] - x[2], 2.0) + pow(y[1] - y[2], 2.0)); double c = sqrt(pow(x[2] - x[0], 2.0) + pow(y[2] - y[0], 2.0)); double s = (a+b+c)/2.0; printf("%.3f\n", sqrt(s*(s-a)*(s-b)*(s-c))); }
D問題
ビット全探索で最大クリークを求める。
bitset
とかいう便利ライブラリがあることを知った。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N, M; cin >> N >> M; vector<vector<int> > e(N, vector<int>(N, 0)); REP(i, M) { int x, y; cin >> x >> y; --x; --y; e[x][y] = e[y][x] = 1; } int ans = 0; for(int bit=1; bit<(1<<N); ++bit) { int t = bitset<12>(bit).count(); if(t <= ans) continue; bool flag = true; REP(i, N) { REP(j, i) { if((bit >> i & bit >> j & 1) && e[i][j] != 1) { flag = false; } } } if(flag) ans = t; } cout << ans << endl; }
Submission #1024133 - AtCoder Beginner Contest 002 | AtCoder
ABC 001
A問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int a, b; cin >> a >> b; cout << a-b << endl; }
Submission #1024112 - AtCoder Beginner Contest 001 | AtCoder
B問題
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int m; cin >> m; int VV; if(m < 100) VV = 0; else if(m <= 5000) VV = m*10/1000.0; else if(m >= 6000 && m <= 30000) VV = m/1000.0+50; else if(m >= 35000 && m <= 70000) VV = (m/1000.0-30)/5.0 + 80; else if(m >= 70000) VV = 89; printf("%02d\n", VV); }
Submission #1024109 - AtCoder Beginner Contest 001 | AtCoder
C問題
やるだけなんだけど、バグる。
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int Deg, Dis; string a; int b; cin >> Deg >> Dis; int I = (Dis/6.0 + 0.5); double D = double(I) / 10.0; if (D >= 0.0 && D <= 0.2) a = "C"; else if(Deg >= 112.5 && Deg < 337.5) a = "NNE"; else if(Deg >= 337.5 && Deg < 562.5) a = "NE"; else if(Deg >= 562.5 && Deg < 787.5) a = "ENE"; else if(Deg >= 787.5 && Deg < 1012.5) a = "E"; else if(Deg >= 1012.5 && Deg < 1237.5) a = "ESE"; else if(Deg >= 1237.5 && Deg < 1462.5) a = "SE"; else if(Deg >= 1462.5 && Deg < 1687.5) a = "SSE"; else if(Deg >= 1687.5 && Deg < 1912.5) a = "S"; else if(Deg >= 1912.5 && Deg < 2137.5) a = "SSW"; else if(Deg >= 2137.5 && Deg < 2362.5) a = "SW"; else if(Deg >= 2362.5 && Deg < 2587.5) a = "WSW"; else if(Deg >= 2587.5 && Deg < 2812.5) a = "W"; else if(Deg >= 2812.5 && Deg < 3037.5) a = "WNW"; else if(Deg >= 3037.5 && Deg < 3262.5) a = "NW"; else if(Deg >= 3262.5 && Deg < 3487.5) a = "NNW"; else a = "N"; if (D >= 0.0 && D <= 0.2) b = 0; else if(D >= 0.3 && D <= 1.5) b = 1; else if(D >= 1.6 && D <= 3.3) b = 2; else if(D >= 3.4 && D <= 5.4) b = 3; else if(D >= 5.5 && D <= 7.9) b = 4; else if(D >= 8.0 && D <= 10.7) b = 5; else if(D >= 10.8 && D <= 13.8) b = 6; else if(D >= 13.9 && D <= 17.1) b = 7; else if(D >= 17.2 && D <= 20.7) b = 8; else if(D >= 20.8 && D <= 24.4) b = 9; else if(D >= 24.5 && D <= 28.4) b = 10; else if(D >= 28.5 && D <= 32.6) b = 11; else if(D >= 32.7) b = 12; cout << a << " " << b << endl; }
Submission #1024104 - AtCoder Beginner Contest 001 | AtCoder
D問題
いもす法
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; int main(void) { int N, S, E; cin >> N; vector<int> record(24*12+1, 0); REP(i, N) { scanf("%d-%d", &S, &E); record[(S/100)*12 + (S%100)/5] += 1; record[(E/100)*12 + (E%100)/5 + ((E%100)%5 > 0 ? 1 : 0)] -= 1; } int t = 0; int start_time = 0; REP(i, record.size()) { if(t == 0 && record[i] > 0) { printf("%02d%02d-", i/12, (i%12) * 5); } if(t > 0 && t + record[i] == 0) { printf("%02d%02d\n", i/12, (i%12) * 5); } t += record[i]; } }
Submission #1024090 - AtCoder Beginner Contest 001 | AtCoder
AOJ 2005: Water Pipe Construction
そすうライブラリのverifyに使われていたので解いてみた。
問題
Water Pipe Construction | Aizu Online Judge
- 有向グラフと各辺のコストが与えられる。
- 頂点
s
から頂点g1
とg2
を結ぶコスト最小の道を作るときのコストを求めよ
解法
全点対間の最小コストを求めておいて、全ての頂点v
について「s
からv
の最小コスト」+「v
からg1
の最小コスト」+「v
からg2
の最小コスト」を調べて最小となるコストを返せばよい。
ダイクストラ
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; struct edge { int src, dst, cost; edge(int s, int t, int c): src(s), dst(t), cost(c) {} }; const int INF = 1e8; void dijkstra(const vector<vector<edge> > &G, vector<int> &d, const int s) { d.assign(d.size(), INF); d[s] = 0; typedef pair<int, int> P; priority_queue<P, vector<P>, greater<P> > que; que.push(P(0, s)); while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; for(auto &e : G[v]) { if(d[e.dst] > d[v] + e.cost) { d[e.dst] = d[v] + e.cost; que.push(P(d[e.dst], e.dst)); } } } } int main(void) { int n, m, s, g1, g2; while(cin >> n >> m >> s >> g1 >> g2 && n) { vector<vector<edge> > G(n); vector<vector<int> > d(n, vector<int>(n)); --s; --g1; --g2; REP(i, m) { int b1, b2, c; cin >> b1 >> b2 >> c; G[b1-1].push_back(edge(b1-1, b2-1, c)); } REP(i, n) { dijkstra(G, d[i], i); } int cost = numeric_limits<int>::max(); REP(i, n) { cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]); } cout << cost << endl; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098833
ベルマン・フォード
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; struct edge { int src, dst, cost; edge(int s, int t, int c): src(s), dst(t), cost(c) {} }; const int INF = 1e8; void bellman_ford(const vector<edge> &edges, vector<int> &d, const int s) { d.assign(d.size(), INF); d[s] = 0; for(auto &i : d) { for(auto &e : edges) { d[e.dst] = min(d[e.dst], d[e.src] + e.cost); } } } int main(void) { int n, m, s, g1, g2; while(cin >> n >> m >> s >> g1 >> g2 && n) { vector<edge> edges; vector<vector<int> > d(n, vector<int>(n)); --s; --g1; --g2; REP(i, m) { int b1, b2, c; cin >> b1 >> b2 >> c; edges.push_back(edge(b1-1, b2-1, c)); } REP(i, n) { bellman_ford(edges, d[i], i); } int cost = numeric_limits<int>::max(); REP(i, n) { cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]); } cout << cost << endl; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098843
ベルマン・フォードは次のような実装でもよい。
void bellman_ford(const vector<edge> &edges, vector<int> &d, const int s) { d.assign(d.size(), INF); d[s] = 0; for(int i=0; i < edges.size(); ++i) { edge e = edges[i]; if (d[e.dst] > d[e.src] + e.cost) { d[e.dst] = d[e.src] + e.cost; i = -1; } } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098773
ワーシャル・フロイド
#include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) #define FOR(i,k,n) for(int i=(k);i<(int)(n);++i) typedef long long int ll; using namespace std; struct edge { int src, dst, cost; edge(int s, int t, int c): src(s), dst(t), cost(c) {} }; const int INF = 1e8; void warshall_floyd(vector<vector<int> > &d, vector<edge> &edges) { for(size_t i=0; i<d.size(); ++i) { d[i].assign(d[i].size(), INF); d[i][i] = 0; } for(auto &e : edges) { d[e.src][e.dst] = e.cost; } const size_t n = d.size(); for(size_t j=0; j<n; ++j) { for(size_t i=0; i<n; ++i) { for(size_t k=0; k<n; ++k) { d[i][k] = min(d[i][k], d[i][j] + d[j][k]); } } } } int main(void) { int n, m, s, g1, g2; while(cin >> n >> m >> s >> g1 >> g2 && n) { vector<edge> edges; vector<vector<int> > d(n, vector<int>(n, INF)); --s; --g1; --g2; REP(i, m) { int b1, b2, c; cin >> b1 >> b2 >> c; edges.push_back(edge(b1-1, b2-1, c)); } warshall_floyd(d, edges); int cost = numeric_limits<int>::max(); REP(i, n) { cost = min(cost, d[s][i] + d[i][g1] + d[i][g2]); } cout << cost << endl; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2098872
追記: 添字の順番を間違えたワーシャル・フロイド
KIJ (正しい)
for(size_t k=0; k<n; ++k) { for(size_t i=0; i<n; ++i) { for(size_t j=0; j<n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }
AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455812
KJI (KIJと同じはず)
for(size_t k=0; k<n; ++k) { for(size_t j=0; j<n; ++j) { for(size_t i=0; i<n; ++i) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }
AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455808
IJK
for(size_t i=0; i<n; ++i) { for(size_t j=0; j<n; ++j) { for(size_t k=0; k<n; ++k) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }
WA: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455813
IJK x 3
for(size_t i=0; i<n; ++i) { for(size_t j=0; j<n; ++j) { for(size_t k=0; k<n; ++k) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(size_t i=0; i<n; ++i) { for(size_t j=0; j<n; ++j) { for(size_t k=0; k<n; ++k) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(size_t i=0; i<n; ++i) { for(size_t j=0; j<n; ++j) { for(size_t k=0; k<n; ++k) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }
AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455814
IKJ x 3
for(size_t i=0; i<n; ++i) { for(size_t k=0; k<n; ++k) { for(size_t j=0; j<n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(size_t i=0; i<n; ++i) { for(size_t k=0; k<n; ++k) { for(size_t j=0; j<n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(size_t i=0; i<n; ++i) { for(size_t k=0; k<n; ++k) { for(size_t j=0; j<n; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }
AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455815
JIK x 3
for(size_t j=0; j<n; ++j) { for(size_t i=0; i<n; ++i) { for(size_t k=0; k<n; ++k) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(size_t j=0; j<n; ++j) { for(size_t i=0; i<n; ++i) { for(size_t k=0; k<n; ++k) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(size_t j=0; j<n; ++j) { for(size_t i=0; i<n; ++i) { for(size_t k=0; k<n; ++k) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }
AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455817
JKI x 3
for(size_t j=0; j<n; ++j) { for(size_t k=0; k<n; ++k) { for(size_t i=0; i<n; ++i) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(size_t j=0; j<n; ++j) { for(size_t k=0; k<n; ++k) { for(size_t i=0; i<n; ++i) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(size_t j=0; j<n; ++j) { for(size_t k=0; k<n; ++k) { for(size_t i=0; i<n; ++i) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }
AC: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3455819