状态dp

所有可能的路线共有(n-1)!种，这个值十分大，即使本题中的n已经很小，仍然无法遍历每一种情况~可以尝试用dp来解决。
写出递推式
假设现在已经访问过的顶点的集合（起点0当作还未访问过的顶点）为S，当前所在的顶点为v，用dp[S][v]表示从v出发访问剩余的所有顶点，最终回到顶点0的路径的权重总和的最小值。由于从v出发可以移动到任意的一个节点u不属于S，因此有如下递推式

dp[V][0]=0
dp[S][v]=min{dp[SU{u}][u]+d(v,u)|u不属于S}

在这个递推式中，有一个下标是集合而不是欧通的整数，所以需要稍加处理。首先试着用记忆化搜索求解。虽然有一个下标不是整数，但是我们可以把它编码成一个整数，或者给它们定义一个全序关系并用二叉搜索树存储，从而可以使用记忆化搜索来求解。另外，对于集合，我们可以把每一个元素的选取与否对应到一个二进制位里，从而把状态压缩成一个整数，大大方便了计算和维护。
以下代码采用的是位运算参考博客

//输入
int n;
int d[MAX_N][MAX_N];

int dp[1<<MAX_N][MAX_N];//记忆话搜索使用的数组

//已经访问锅的节点的集合为S，当前位置为v
int rec(int S,int v){
    if(dp[S][v]>0)
        return dp[S][v];
    //已经访问锅所有节点并回到0号点
    //从一个0个顶点（2^0）向左移动了n位所以是（1<<n）
    //又因为S是从0开始的，所以减去1
    if(S==(1<<n)-1&&v==0)
        return dp[S][v]=0;
    int res=INF;
    for(int u=0;u<n;u++){
        //如果S从右边数起第u位为假
        if(!(S>>u&1)){
            //下一步移动到顶点u
            //s|)(1<<u) 对第u位赋值为1
            res=min(res,rec(S|1<<u,u)+d[v][u]);
        }
    }
    return dp[S][v]=res;
}

void solve(){
    memset(dp,-1,sizeof(dp));
    cout<<rec(0,0);
}

这样就可以在O(2ⁿ n²)时间内完成计算。对于不是整数的情况，很多时候很难确定一个合适的地推顺序，因此使用记忆话搜索可以避免这个问题。不过在这个问题中，对于任意两个整数i和j，如果他们对应的集合满足S(i)属于S(j)，就有i≤j，因此还可以像下面的写法一样，通过循环求出答案。

int dp[1<<MAX_N][MAX_N];

void solve(){
    //用足够大的值初始化数组
    for(int S=0;S<1<<n;S++){
        fill(dp[S],dp[S]+n,INF);
    }
    dp[(1<<n)-1][0]=0;

    //根据递推式依次计算
    for(int S=(1<<n)-2;S>=0;S--){
        for(int v=0;v<n;v++){
            for(int u=0;u<n;u++){
                if(!(S>>u&&1)){
                    dp[S][v]=min(dp[S][v],dp[S|1<<u][u]+d[v][u]);
                }
            }
        }
    }
    cout<<dp[0][0];
}

poj2686
虽然可以把城市看作顶点，道路看作边建图，但是由于有车票相关的限制，无法直接使用Dijkstra算法求解。不过这种情况下只需要把状态看作顶点，把状态的转移看成边来建图就可以很好的避免这个问题。
先考虑一下“现在在城市v，此时还剩下的车票的集合为S”这样的状态，从这个状态出发，使用一张车票i∈S移动到相邻的城市u，就相当于转移到了“在城市u，此时还剩下的车片的集合为S{i}”这个状态。把这个转移看成一条边，那么边上的花费是（v-u间道路的长度）/ti。按照上述方法所构的图，就可以用普通的Dijkstra算法求解了。
集合S使用状态压缩的方法表示就可以了。由于剩余的车票的集合S随着移动元素个数不断变小，因此这个图实际上是个DAG。计算DAG的最短路不需要使用Dijkstra算法，可以简单地通过DP求解，如图：