ABC 004

abc004.contest.atcoder.jp

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

abc005.contest.atcoder.jp

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]に入れる。 O(N^2)
  • (x, y, w, h)を指定したらその長方形のおいしさの和を返す関数がarea。 O(1)
  • 全ての高さ・幅の長方形に対して最大のおいしさを求める。 O(N^4)
  • 各たこ焼き数以下で達成できる最大のおいしさを求める。 O(N^2)
  • 以上の準備をすれば、各店員の焼けるたこ焼き数に対する最大のおいしさが O(1)で求まる。
#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

abc003.contest.atcoder.jp

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

abc002.contest.atcoder.jp

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

abc001.contest.atcoder.jp

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

追記: 添字の順番を間違えたワーシャル・フロイド

qiita.com

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

AOJ 1608: Selection of Participants of an Experiment

問題

Selection of Participants of an Experiment | Aizu Online Judge

  • 数列の中で最も差の小さい2つの数の差を出力する

コード

#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;
    vector<int> a;
    while(cin >> n && n) {
        a.resize(n);
        REP(i, n) cin >> a[i];
        int ans = numeric_limits<int>::max();
        sort(a.begin(), a.end());
        REP(i, n-1) ans = min(ans, a[i+1]-a[i]);
        cout << ans << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2094065