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
", 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
", 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;

}