0

サイトでプログラミングの問題を解決していました。私のマシン (Visual Studio 2010) では、テスト ケースで間違った結果が得られますが、サイトでは正しい結果が得られます。サイトの審査員のコンパイラが何かわかりませんが、gccかcygwinのようなものだと思います。

コード

グラフの問題です。ここでのグラフはツリーとして表されます。グラフは有向で、ループは含まれていません。解決策は(2 * sum of all edges - max path length from root)

//     to-vertex & edge-length
vector<pair<int, int> > pr[100];
int dfs(int i) // to find max path length from root
{
    int mx = 0;
    for (int j = 0; j < pr[i].size(); ++j)
        mx = max(mx, dfs(pr[i][j].first) + pr[i][j].second);
    return mx;
}

int PowerOutage::estimateTimeOut(vector <int> from_vertex,
                 vector <int> to_vertex, vector <int> edge_length)
{
    int tot = 0;
    for (int i = 0; i < from_vertex.size(); ++i)
    {
        pr[from_vertex[i]].push_back(make_pair(to_vertex[i], edge_length[i]));
        tot += (2 * edge_length[i]);
    }
    return tot - dfs(0);
}

テストケース

from_vertex   {0,     0,   0,   0,   0}
to_vertex     {1,     2,   3,   4,   5}
edge_length   {100, 200, 300, 400, 500}

Visual Studio は 2493 を返しますが、サイトのコンパイラは正しい答えを返します: 2500。

2 つの結果が異なるのはなぜですか? VSに表示されて間違った答えを出しますが、他のコンパイラでは消えてしまう隠れたバグが(私のコードに)あると思います。サイトのコンパイラを特定し、代わりに使用する必要がありますか?

4

1 に答える 1

0

私の最初の（間違った）仮定にもかかわらず、OPはすでに2500であることがわかりましたが、「2500はどこに印刷されていますか?」と尋ねた後、テスト機能に欠陥がありました。

于 2012-09-02T07:33:37.687 に答える