メモ

自分に向けて書いたメモを取り扱っています.

AOJ 0244 Hot Spring Trip

方針

深さ優先探索
特殊な切符を使って頂点nにたどり着いた時の最小コストがdict[0][n],使わなかったときdict[1][n]です.

コード

const int INF = 1 << 30;

int N, M;
int G[100][100];
int dict[2][100];
vector<int> A[100];

//n:今の場所
//c:特殊な切符
//sum:料金

void dfs(int n, bool c, int sum)
{
    if(dict[c][n] <= sum)
        return;

    dict[c][n] = sum;

    for(int i = 0; i < A[n].size(); i++)
    {
        int prev = A[n][i];

        dfs(prev, c, sum + G[n][prev]);

        if(c)
            for(int j = 0; j < A[prev].size(); j++)
                dfs(A[prev][j], false, sum);
    }
}

int main()
{
    int a, b, c;

    while(cin >> N >> M, N|M)
    {
        for(int i = 0; i < 2; i++)
            fill(dict[i], dict[i] + N, INF);

        for(int i = 0; i < N; i++)
            A[i].clear();

        N--;

        for(int i = 0; i < M; i++)
        {
            cin >> a >> b >> c;
            a--, b--;
            G[a][b] = G[b][a] = c;
            A[a].push_back(b);
            A[b].push_back(a);
        }

        dfs(0, true, 0);

        cout << min(dict[0][N], dict[1][N]) << endl;
    }
}