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

然后是SPFA

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

补充：软件开发 , C++ ,