HDOJ 3790 最短路径问题（边有两个属性）

http://acm.hdu.edu.cn/showproblem.php?pid=3790

题意：
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

分析：
这道题边不仅有权值，还多了一个花费属性，在松弛边的时候如果d[E.to] == d[vNo] + E.w 且 c[E.to] > c[vNo] + E.c的话就更新E.to顶点的（从起点到E.to）花费值。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <functional>
using namespace std;
const int
MAXV = 1005, MAXE = 100005, INF = 0x3f3f3f3f;
typedef pair<int, int> pr;

struct edge {
    int to, w, c;
};
vector<vector<edge> > lj(MAXV);
int v, e;
int d[MAXV], c[MAXV];

edge tempEdge(int t, int w, int c) {
    edge ret;
    ret.to = t;
    ret.w = w;
    ret.c = c;
    return ret;
}
void Dijkstra(int s) {
    priority_queue<pr, vector<pr>, greater<pr> > q;
    fill(d + 1, d + v + 1, INF);
    d[s] = 0;
    c[s] = 0;
    q.push(pr(s, 0));

    while (!q.empty()) {
        pr v = q.top();
        q.pop();
        int vNo = v.first;
        if (d[vNo] < v.second)
            continue;
        for (edge E : lj[vNo]) {
            if (d[E.to] > d[vNo] + E.w) {
                d[E.to] = d[vNo] + E.w;
                c[E.to] = c[vNo] + E.c;
                q.push(pr(E.to, d[E.to]));
            }
            else if (d[E.to] == d[vNo] + E.w && c[E.to] > c[vNo] + E.c) {
                c[E.to] = c[vNo] + E.c;
            }
        }
    }
}

int main() {
    while (scanf("%d%d", &v, &e) != EOF && v && e) {
        for (int i = 1; i <= v; ++i)
            lj[i].clear();
        for (int i = 1; i <= e; ++i) {
            int f, t, w, c;
            scanf("%d%d%d%d", &f, &t, &w, &c);
            lj[f].push_back(tempEdge(t, w, c));
            lj[t].push_back(tempEdge(f, w, c));
        }
        int s, t;
        scanf("%d%d", &s, &t);
        Dijkstra(s);
        printf("%d %d\n", d[t], c[t]);
    }
    return 0;
}