题目链接

Mr. Rito Post Office Aizu - 2200

思路

$$ 先预处理海路和陆路的最短路，然后dp\\\\dp[i][j]表示到达第i个目的地时船停在j处时的最小值\\\\ $$

时间复杂度

$$ O(RN^2) $$

代码

#include <cstdio>
#include <vector>

using namespace std;

const long long INF = 1e16;

class Floyd {
public:
    typedef long long T;

    vector<vector<T> > dist;
    int n;

    void init(int _n) {
        n = _n;
        vector<T> temp(n + 5);
        dist.resize(n + 5, temp);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dist[i][j] = INF;
                if (i == j) {
                    dist[i][j] = 0;
                }
            }
        }
    }

    void add_edge(int u, int v, T w) {
        dist[u][v] = min(dist[u][v], w);
    }

    void add_edges(int u, int v, T w) {
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    void gao() {
        for (int k = 0; k <= n; k++) {
            for (int i = 0; i <= n; i++) {
                for (int j = 0;j <= n; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

};

const int MAXN = 210;

long long dp[2][MAXN];
int a[1010];

int main() {
    int n, m;

    while (scanf("%d%d", &n, &m), n + m) {
        Floyd ds, dl;
        ds.init(n);
        dl.init(n);
        int x, y, t;
        char op[5];
        while (m--) {
            scanf("%d%d%d", &x, &y, &t);// don't forget &
            scanf("%s", op);// no &
            if (op[0] == 'L') {
                dl.add_edges(x, y, t);
            } else {
                ds.add_edges(x, y, t);
            }
        }
        int r;
        scanf("%d", &r);// don't forget &
        for (int i = 1; i <= r; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        dl.gao();
        ds.gao();
        for (int i = 1; i <= n; i++) {
            dp[1][i] = INF;
        }
        dp[1][a[1]] = 0;
        for (int i = 2; i <= r; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i & 1][j] = dp[(i - 1) & 1][j] + dl.dist[a[i - 1]][a[i]];
                for (int k = 1; k <= n; k++) {
                    dp[i & 1][j] = min(dp[i & 1][j], dp[(i - 1) & 1][k] + dl.dist[a[i - 1]][k] + ds.dist[k][j] + dl.dist[j][a[i]] );
                }
            }
        }
        long long ans = INF;
        for (int i = 1; i <= n; i++) {
            ans = min(ans, dp[r & 1][i]);
        }
        printf("%lld\n", ans);
    }


    return 0;
}