2011-11-12 08:13:00Morris
a269. 小氣的國王
a269. 小氣的國王
/**********************************************************************************/
/* Problem: a269 "小氣的國王" from */
/* Language: C (1909 Bytes) */
/* Result: AC(200ms, 1.6MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-11-12 08:05:19 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 100000000
#define MaxN 10001
typedef struct {
short x, y, v, c;
}Path;
Path D[40001];
int NodeL[10001], NodeT[10001];
int cmp(const void *i, const void *j) {
Path *a, *b;
a = (Path *)i, b = (Path *)j;
if(a->x != b->x)
return a->x - b->x;
else {
if(a->v != b->v)
return a->v - b->v;
else
return a->c - b->c;
}
}
int SPFA(int n, int st) {
static unsigned short Q[MaxN], Qt, i, j, k, head, tail, Used[MaxN], tn;
static int V[MaxN];
for(i = 1; i <= n; i++)
V[i] = oo, Used[i] = 0;
Qt = -1, Q[++Qt] = st, head = Qt, tail = Qt, Used[st] = 1, V[st] = 0;
for(i = 0; i <= Qt; i++) {
tn = Q[head], Used[tn] = 0, head++;
if(head >= n) head -= n;
for(j = 0, k = NodeL[tn]; j < NodeT[tn]; j++, k++) {
if(V[tn]+D[k].v < V[D[k].y]) {
V[D[k].y] = V[tn]+D[k].v;
if(Used[D[k].y] == 0) {
++tail;
if(tail >= n) tail -= n;
Used[D[k].y] = 1, Q[tail] = D[k].y, Qt++;
}
}
}
}
int Cost = 0, dis, min_cost;
for(i = 1; i <= n; i++) {
tn = i, dis = V[i];
if(tn == st) continue;
min_cost = oo;
for(j = 0, k = NodeL[tn]; j < NodeT[tn]; j++, k++) {
if(dis == V[D[k].y] + D[k].v)
min_cost = min_cost < D[k].c ? min_cost : D[k].c;
}
Cost += min_cost;
}
return Cost;
}
int main() {
int n, m, i;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0) break;
for(i = 0; i < m; i++) {
scanf("%hd %hd %hd %hd", &D[i].x, &D[i].y, &D[i].v, &D[i].c);
D[m+i].x = D[i].y, D[m+i].y = D[i].x, D[m+i].v = D[i].v, D[m+i].c = D[i].c;
}
m <<= 1;
qsort(D, m, sizeof(Path), cmp);
for(i = 1; i <= n; i++)
NodeL[i] = oo, NodeT[i] = 0;
for(i = 0; i < m; i++) {
NodeL[D[i].x] = NodeL[D[i].x] < i ? NodeL[D[i].x] : i;
NodeT[D[i].x]++;
}
printf("%d\n", SPFA(n, 1));
}
return 0;
}
內容 ：
身為一個國王，你對於你的國家（由n個城市組成）
竟然沒有任何一條道路感到不可思議！
大臣感受到您的憤怒後立刻遞上了一份道路建構計畫
但勤儉持國的你決定要在砍個預算，也就是把一些路從計畫中拿掉
但是為了交通順暢，你必須保證拿掉之後從首都到每個城市的最短距離不能變長
請問你至少要花多少錢來蓋路呢～
噢對了，首都在編號一的城市
輸入說明 ：
多組輸入，以EOF作為結束
每組輸入第一行有兩個正整數n(1<=n<=10000)，m(0<=m<=20000)
分別代表城市以及計畫中道路的數量，保證原計畫中首都可以到達所有城市
接下來m行每行有四個整數u,v,d,c(1<=u,v<=n,u!=v,1<=d<=10000,1<=c<=1000)
代表計畫中有一條連接u,v的雙向道路，長度為d，成本為c
輸出說明 ：
一個數字，代表至少要花多少錢在計畫中
範例輸入 ：
3 31 2 1 22 3 2 13 1 3 25 51 2 2 22 3 1 11 4 1 14 5 1 15 3 1 15 101 2 32 101 3 43 431 4 12 521 5 84 232 3 58 422 4 86 992 5 57 833 4 11 323 5 75 214 5 23 435 101 2 1 531 3 1 651 4 1 241 5 1 762 3 1 192 4 1 462 5 1 253 4 1 133 5 1 654 5 1 340 0
範例輸出 ：
35137218
提示 ：
在第一組範例中僅需計畫中前兩條道路即可
出處 ：
/**********************************************************************************/
/* Problem: a269 "小氣的國王" from */
/* Language: C (1909 Bytes) */
/* Result: AC(200ms, 1.6MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-11-12 08:05:19 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 100000000
#define MaxN 10001
typedef struct {
short x, y, v, c;
}Path;
Path D[40001];
int NodeL[10001], NodeT[10001];
int cmp(const void *i, const void *j) {
Path *a, *b;
a = (Path *)i, b = (Path *)j;
if(a->x != b->x)
return a->x - b->x;
else {
if(a->v != b->v)
return a->v - b->v;
else
return a->c - b->c;
}
}
int SPFA(int n, int st) {
static unsigned short Q[MaxN], Qt, i, j, k, head, tail, Used[MaxN], tn;
static int V[MaxN];
for(i = 1; i <= n; i++)
V[i] = oo, Used[i] = 0;
Qt = -1, Q[++Qt] = st, head = Qt, tail = Qt, Used[st] = 1, V[st] = 0;
for(i = 0; i <= Qt; i++) {
tn = Q[head], Used[tn] = 0, head++;
if(head >= n) head -= n;
for(j = 0, k = NodeL[tn]; j < NodeT[tn]; j++, k++) {
if(V[tn]+D[k].v < V[D[k].y]) {
V[D[k].y] = V[tn]+D[k].v;
if(Used[D[k].y] == 0) {
++tail;
if(tail >= n) tail -= n;
Used[D[k].y] = 1, Q[tail] = D[k].y, Qt++;
}
}
}
}
int Cost = 0, dis, min_cost;
for(i = 1; i <= n; i++) {
tn = i, dis = V[i];
if(tn == st) continue;
min_cost = oo;
for(j = 0, k = NodeL[tn]; j < NodeT[tn]; j++, k++) {
if(dis == V[D[k].y] + D[k].v)
min_cost = min_cost < D[k].c ? min_cost : D[k].c;
}
Cost += min_cost;
}
return Cost;
}
int main() {
int n, m, i;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0) break;
for(i = 0; i < m; i++) {
scanf("%hd %hd %hd %hd", &D[i].x, &D[i].y, &D[i].v, &D[i].c);
D[m+i].x = D[i].y, D[m+i].y = D[i].x, D[m+i].v = D[i].v, D[m+i].c = D[i].c;
}
m <<= 1;
qsort(D, m, sizeof(Path), cmp);
for(i = 1; i <= n; i++)
NodeL[i] = oo, NodeT[i] = 0;
for(i = 0; i < m; i++) {
NodeL[D[i].x] = NodeL[D[i].x] < i ? NodeL[D[i].x] : i;
NodeT[D[i].x]++;
}
printf("%d\n", SPFA(n, 1));
}
return 0;
}