http://acm.hdu.edu.cn/showproblem.php?pid=3790
題意：
給你n個(gè)點(diǎn)精耐，m條無向邊，每條邊都有長(zhǎng)度d和花費(fèi)p普碎，給你起點(diǎn)s終點(diǎn)t捐顷，要求輸出起點(diǎn)到終點(diǎn)的最短距離及其花費(fèi)践瓷，如果最短距離有多條路線，則輸出花費(fèi)最少的。
分析：
這道題邊不僅有權(quán)值，還多了一個(gè)花費(fèi)屬性搭综，在松弛邊的時(shí)候如果d[E.to] == d[vNo] + E.w 且 c[E.to] > c[vNo] + E.c的話就更新E.to頂點(diǎn)的（從起點(diǎn)到E.to）花費(fèi)值垢箕。
#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;
}
