AOJ 0244: Hot Spring

色々やり方があると思いますが, 僕は枝刈りDFSしました.

このコードを載せておいてなんですが, N^3全探索がオススメです.

#include <cstdio>
#include <cstring>
#include <vector>

#define MAX_N (100)
#define INF (100000000)

using namespace std;

typedef struct {
    int to;
    int cost;
} Edge;

vector<Edge> G[MAX_N];
int W[MAX_N][MAX_N];

int ans;
int n, m;

void getMin(int V, int cost, int left, bool used[][MAX_N])
{
    if (cost >= ans){
        return;
    }
    
    if (V == n - 1){
        if ((left == 2 || left == 0) && ans > cost){
            ans = cost;
        }
    }
    
    if (left == 2){
        for (int i = 0; i < G[V].size(); i++){
            if (used[V][G[V][i].to] == false){
                used[V][G[V][i].to] = true;
                getMin(G[V][i].to, cost + G[V][i].cost, left, used);
                getMin(G[V][i].to, cost, left - 1, used);
                used[V][G[V][i].to] = false;
            }
        }
    }
    if (left == 1){
        for (int i = 0; i < G[V].size(); i++){
            if (used[V][G[V][i].to] == false){
                used[V][G[V][i].to] = true;
                getMin(G[V][i].to, cost, left - 1, used);
                used[V][G[V][i].to] = false;
            }
        }
    }
    if (left == 0){
        getMin(n - 1, cost + W[V][n - 1], 0, used);
    }
    
    return;
}

int main()
{
    int a, b, c;
    Edge in;
    
    while (1){
        scanf("%d %d", &n, &m);
        
        if (n + m == 0){
            break;
        }
        
        for (int i = 0; i < n; i++){
            G[i].clear();
        }
        
        for (int i = 0; i < n; i++){
            fill(W[i], W[i] + n, INF);
            W[i][i] = 0;
        }
        
        for (int i = 0; i < m; i++){
            scanf("%d %d %d", &a, &b, &c);
            
            in.to = --a;
            in.cost = c;
            G[--b].push_back(in);
            in.to = b;
            G[a].push_back(in);
            
            W[a][b] = W[b][a] = c;
        }
        
        for (int k = 0; k < n; k++){
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++){
                    W[i][j] = min(W[i][j], W[i][k] + W[k][j]);
                }
            }
        }
        
        bool used[MAX_N][MAX_N];
        
        for (int i = 0; i < n; i++){
            fill(used[i], used[i] + n, false);
        }
        
        ans = INF;
        getMin(0, 0, 2, used);
        
        printf("%d\n", ans);
    }
    
    return (0);
}