Road Construction
Time limit 8000 ms
Memory limit 131072 kB
Problem Description
出若干个建筑之间的一些路，每条路都有对应的长度和需要的花费，问在保证源点1 到其他个点的距离最短的情况下，最少的花费是多少
Input
The input consists of several datasets. Each dataset is formatted as follows.
N M
u1 v1 d1 c1
.
.
.
uM vM dM cM
The first line of each dataset begins with two integers, N and M (1 ≤ N ≤ 10000, 0 ≤ M ≤ 20000). N and M indicate the number of cities and the number of roads in the original plan, respectively.
The following M lines describe the road information in the original plan. The i-th line contains four integers, ui, vi, di and ci (1 ≤ ui, vi ≤ N , ui ≠ vi , 1 ≤ di ≤ 1000, 1 ≤ ci ≤ 1000). ui , vi, di and ci indicate that there is a road which connects ui-th city and vi-th city, whose length is di and whose cost needed for construction is ci.
Each road is bidirectional. No two roads connect the same pair of cities. The 1-st city is the capital in the kingdom.
The end of the input is indicated by a line containing two zeros separated by a space. You should not process the line as a dataset.
Output
For each dataset, print the minimum cost of a plan which satisfies the conditions in a line.
Sample Input
3 3
1 2 1 2
2 3 2 1
3 1 3 2
5 5
1 2 2 2
2 3 1 1
1 4 1 1
4 5 1 1
5 3 1 1
5 10
1 2 32 10
1 3 43 43
1 4 12 52
1 5 84 23
2 3 58 42
2 4 86 99
2 5 57 83
3 4 11 32
3 5 75 21
4 5 23 43
5 10
1 2 1 53
1 3 1 65
1 4 1 24
1 5 1 76
2 3 1 19
2 4 1 46
2 5 1 25
3 4 1 13
3 5 1 65
4 5 1 34
0 0
Output for the Sample Input
3
5
137
218
解题心得：
- 其实要解决的就两个问题，第一个是要保证路径的长度一定要是最小的，在路径最小的情况下要保证花费最少，还是比较容易解决的，首先还是维护最短路嘛，记录到当前节点的使用的边是哪一条边，然后如果都是最短的路就更新更短的边就可以了。
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e4+100;
struct City {
int to,len,va;
};
struct Spend {
int len,va;
}sp[maxn];
vector <City> ve[maxn];
int n,m;
bool vis[maxn];
void init() {
for(int i=1;i<=n;i++) {
sp[i].va = sp[i].len = 0x7f7f7f7f;
ve[i].clear();
}
City temp;
for(int i=0;i<m;i++) {
int a,b,len,va;
scanf("%d%d%d%d",&a,&b,&len,&va);
temp.to = b,temp.len = len,temp.va = va;
ve[a].push_back(temp);
temp.to = a;
ve[b].push_back(temp);
}
}
void spfa() {
sp[1].len = sp[1].va = 0;
queue <int> qu;
qu.push(1);
while(!qu.empty()) {
int now = qu.front(); qu.pop();
vis[now] = false;
for(int i=0;i<ve[now].size();i++) {
City temp = ve[now][i];
int v = temp.to;
int d = temp.len;
int va = temp.va;
if(sp[v].len > sp[now].len + d) {
sp[v].len = sp[now].len + d;
sp[v].va = va;
if(!vis[v]) {
qu.push(v);
vis[v] = true;
}
}
if(sp[v].len == sp[now].len + d && sp[v].va > va) {
sp[v].va = va;
}
}
}
}
void get_len() {
int tot = 0;
for(int i=1;i<=n;i++) {
tot += sp[i].va;
}
printf("%d
",tot);
}
int main() {
while(scanf("%d%d",&n,&m) && n+m) {
init();
spfa();
get_len();
}
return 0;
}