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; } }