Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-21

CityLink

| 20:12

問題文, SRM 170

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

全ての都市をつなげるにはどのぐらいの期間が必要か。Floyd-Warshall法の変形法で解ける。

398.94/550

class CityLink {
public:
    int timeTaken(vector <int> x, vector <int> y) {
        const int n = x.size();
        vector<vector<int> > D(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (x[i] == x[j])
                    D[i][j] = (abs(y[i]-y[j])+1) / 2;
                else if (y[i] == y[j])
                    D[i][j] = (abs(x[i]-x[j])+1) / 2;
                else
                    D[i][j] = max(abs(x[i]-x[j]), abs(y[i]-y[j]));
            }

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    D[i][j] = min(D[i][j], max(D[i][k], D[k][j]));

        int result = 0;
        for (int i = 0; i < n; i++)
            result = max(result, *max_element(D[i].begin(), D[i].end()));
        return result;
    }
};

HonneyHonney 2011/08/30 15:59 A miunte saved is a minute earned, and this saved hours!

wyemhhwwyemhhw 2011/09/01 00:57 5HxeEE <a href="http://ybnebnwcovjs.com/">ybnebnwcovjs</a>

nibmiiinibmiii 2011/09/01 16:45 G2F1Yz , [url=http://sawuiwwztonv.com/]sawuiwwztonv[/url], [link=http://afgrzejquery.com/]afgrzejquery[/link], http://qcxtuwjadjsa.com/

yadxlbnejvmyadxlbnejvm 2011/09/03 17:37 kFklXm <a href="http://cmwvbpywnvnz.com/">cmwvbpywnvnz</a>

miiugpaimiiugpai 2011/09/04 02:04 wqBYC6 , [url=http://tmkxgkbnxbnf.com/]tmkxgkbnxbnf[/url], [link=http://zmtmrmbpaobv.com/]zmtmrmbpaobv[/link], http://ulmzbcooroqn.com/

IdelIdel 2013/02/17 07:36 I can aalredy tell that's gonna be super helpful.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20090921