HDU 3790-最短パス問題(最短+dp)

タイトルリンク
http://acm.hdu.edu.cn/showproblem.php?pid=3790
構想
裸の最短+dpはまずDijkstraを1回走ってd[]配列を得,その後dp:f[v]はノードvの最小費用を表し,遷移方程式:f[v]={min(f[v],f[u]+p(u,v)|d[v]=d[u]+w(u,v)}は辺uからvまでの費用を表し,w(u,v)は辺(u,v)の経路長を表す
詳細

注意重辺

注意初期化

コード#コード#

#include 

using namespace std;

inline int in() {int x; scanf("%d", &x); return x;}
#define pr(x) {cout << #x << ' ' << x << endl;}
#define INF 0x3f3f3f3f
#define PII pair
#define mp make_pair 

const int maxn = 1000 + 5;
struct Edge {
    int u, v, w, p;
    Edge(int a, int b, int c, int d) : u(a), v(b), w(c), p(d) {

    }
};

vector<int> G[maxn];
vector Edges;
int n, m, S, T;
map mm;

void init() {
    for (int i = 0; i <= n; i++) G[i].clear();
    Edges.clear();
    mm.clear();
}

void addedge(int u, int v, int w, int p) {
    Edges.push_back(Edge(u, v, w, p));
    G[u].push_back(Edges.size() - 1);
}

struct cmp {
    bool operator () (PII a, PII b) {
        return b.second < a.second;
    }
};

int d[maxn], vis[maxn];
priority_queuevector, cmp> Q;

void dijkstra(int s) {
    for (int i = 0; i <= n; i++) d[i] = INF;
    d[s] = 0;
    memset(vis, 0, sizeof(vis));
    Q.push(mp(s, d[s]));
    while (!Q.empty()) {
        PII t = Q.top(); Q.pop();
        int u = t.first;
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = 0; i < G[u].size(); i++) {
            Edge e = Edges[G[u][i]];
            if (d[e.v] > d[u] + e.w) {
                d[e.v] = d[u] + e.w;
                Q.push(mp(e.v, d[e.v]));
            }
        }
    }
}

int r[maxn];
bool cmp2(int i, int j) {
    return d[i] < d[j];
}

int dp() {
    int f[maxn];
    for (int i = 0; i <= n; i++) f[i] = INF;
    f[S] = 0;
    for (int i = 1; i <= n; i++) r[i] = i;
    sort(r + 1, r + 1 + n, cmp2);
    for (int ii = 1; ii <= n; ii++) {
        int u = r[ii];
        for (int i = 0; i < G[u].size(); i++) {
            Edge e = Edges[G[u][i]];
            int v = e.v;
            if (d[v] == d[u] + e.w) f[v] = min(f[v], f[u] + e.p);
        }
    }
    return f[T];
}

int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        if (!n && !m) break;
        for (int i = 0; i < m; i++) {
            int x = in(); int y = in(); int w = in(), p = in();
            if (x > y) swap(x, y);
            if (mm[mp(x, y)].first != 0 && mm[mp(x, y)].second != 0) {
                PII &t = mm[mp(x, y)];
                if (w < t.first) t.first = w, t.second = p;
                else if (w == t.first) t.second = min(t.second, p);
            } else {
                mm[mp(x, y)] = mp(w, p);
            }
        }
        S = in(); T = in();
        for (map::iterator it = mm.begin(); it != mm.end(); it++) {
            PII x = it->first, y = it->second;
            addedge(x.first, x.second, y.first, y.second);
            addedge(x.second, x.first, y.first, y.second);
        }
        dijkstra(S);
        int pp = dp();
        printf("%d %d
", d[T], pp);
    }
    return 0;
}