POJ 2686 Traveling by Stagecoach 壯壓DP

大意是有一個人從某個城市要到另一個城市（點數<=30） 然後有n個馬車票，相鄰的兩個城市走的話要消耗掉一個馬車票。 花費的時間呢，是馬車票上有個速率值，用邊/速率就是花的時間。 問最後這個人花費的最短時間是多少   然後就是壯壓DP了 dp[S][v] 代表當前消耗了S集合的車票走到v花費的最小時間 可以用spfa轉移。 也可以直接轉移。 直接轉的原因是，這個圖由於走路要消耗車票，所以實質上圖是個DAG   看兩種代碼    

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <vector>  
#include <algorithm>  
#define MAXN 2222  
#define INF 1000000007  
using namespace std;  
double dp[333][33];  
typedef pair<int, int> P;  
vector<P>g[33];  
int t, n, m, src, des;  
int num[33];  
int main ()  
{  
    int u, v, w;  
    while(scanf("%d%d%d%d%d", &t, &n, &m, &src, &des) != EOF)  
    {  
        if(!t && !n && !m && !src && !des) break;  
        for(int i = 0; i < t; i++) scanf("%d", &num[i]);  
        for(int i = 0; i <= n; i++) g[i].clear();  
        for(int i = 0; i < m; i++)  
        {  
            scanf("%d%d%d", &u, &v, &w);  
            g[u].push_back(make_pair(v, w));  
            g[v].push_back(make_pair(u, w));  
        }  
        for(int i = 0; i <= 300; i++)  
            for(int j = 0; j < 33; j++)  
                dp[i][j] = INF;  
        dp[0][src] = 0;  
        double res = INF;  
        for(int i = 0; i < (1 << t); i++)  
        {  
            for(u = 1; u <= n; u++)  
                 for(int k = 0; k < t; k++)  
                    if(!(i & (1 << k)))  
                    {  
                        for(int j = 0; j < g[u].size(); j++)  
                        {  
                            v = g[u][j].first;  
                            w = g[u][j].second;  
                            dp[i | (1 << k)][v] = min(dp[i | (1 << k)][v], dp[i][u] + (double)w / num[k]);  
                        }  
                    }  
            res = min(res, dp[i][des]);  
        }  
        if(res == INF) puts("Impossible");  
        else printf("%.3f\n", res);  
  
    }  
    return 0;  
}  

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <vector>  
#include <queue>  
#include <algorithm>  
#define MAXN 2222  
#define INF 1000000007  
using namespace std;  
double dp[333][33];  
typedef pair<int, int> P;  
vector<P>g[33];  
int t, n, m, src, des;  
int num[33], vis[333][33];  
queue<P>q;  
void spfa()  
{  
    for(int i = 0; i <= 300; i++)  
        for(int j = 0; j < 33; j++)  
            dp[i][j] = INF;  
    memset(vis, 0, sizeof(vis));  
    dp[0][src] = 0;  
    vis[0][src] = 1;  
    while(!q.empty()) q.pop();  
    q.push(make_pair(0, src));  
    while(!q.empty())  
    {  
        P top = q.front();  
        q.pop();  
        int S = top.first;  
        int u = top.second;  
        for(int j = 0; j < t; j++)  
        {  
            if(S & (1 << j)) continue;  
            for(int i = 0; i < g[u].size(); i++)  
            {  
                int v = g[u][i].first;  
                int w = g[u][i].second;  
                if(dp[S | (1 << j)][v] > dp[S][u] + (double)w / num[j])  
                {  
                    dp[S | (1 << j)][v] = dp[S][u] + (double)w / num[j];  
                    if(!vis[S | (1 << j)][v])  
                    {  
                        q.push(make_pair(S | (1 << j), v));  
                        vis[S | (1 << j)][v] = 1;  
                    }  
                }  
            }  
        }  
    }  
    double res = INF;  
    for(int i = 0; i < (1 << t); i++)  
        res = min(res, dp[i][des]);  
    if(res == INF) puts("Impossible");  
    else printf("%.3f\n", res);  
}  
int main ()  
{  
    int u, v, w;  
    while(scanf("%d%d%d%d%d", &t, &n, &m, &src, &des) != EOF)  
    {  
        if(!t && !n && !m && !src && !des) break;  
        for(int i = 0; i < t; i++) scanf("%d", &num[i]);  
        for(int i = 0; i <= n; i++) g[i].clear();  
        for(int i = 0; i < m; i++)  
        {  
            scanf("%d%d%d", &u, &v, &w);  
            g[u].push_back(make_pair(v, w));  
            g[v].push_back(make_pair(u, w));  
        }  
        spfa();  
    }  
    return 0;  
}