Road Construction

King Mercer is the king of ACM kingdom. There are one capital and some cities in his kingdom. Amazingly, there are no roads in the kingdom now. Recently, he planned to construct roads between the capital and the cities, but it turned out that the construction cost of his plan is much higher than expected.

In order to reduce the cost, he has decided to create a new construction plan by removing some roads from the original plan. However, he believes that a new plan should satisfy the following conditions:

For every pair of cities, there is a route (a set of roads) connecting them.
The minimum distance between the capital and each city does not change from his original plan.

Many plans may meet the conditions above, but King Mercer wants to know the plan with minimum cost. Your task is to write a program which reads his original plan and calculates the cost of a new plan with the minimum cost.

Input

The input consists of several datasets. Each dataset is formatted as follows.

N M
u₁ v₁ d₁ c₁
.
.
.
u_M v_M d_M c_M

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, u_i, v_i, d_i and c_i (1 ≤ u_i, v_i ≤ N , u_i ≠ v_i , 1 ≤ d_i ≤ 1000, 1 ≤ c_i ≤ 1000). u_i , v_i, d_i and c_i indicate that there is a road which connects u_i-th city and v_i-th city, whose length is d_i and whose cost needed for construction is c_i.

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

Output for the Sample Input

3

5

137

218

题解：
　　首先，我把模型抽象出来，就是求一棵单源最短路树，使得这棵树的权值最小。
　　真是，我把这个模型抽象出来之后就马上有想法了，但是wa了，现在还是不知道有什么问题，就是先跑spfa，然后将dis[now]=dis[to]+quan的边扣出来，单独跑一遍最小生成树，但wa了，我现在还不知道为什么。
　　然后换一下思路，对于dis相同的点，我们只要跑spfa时记录一笑dis最小时，以他为去处的最小花费就可以了。
代码：

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

#include <queue>

#define MAXN 100000

using namespace std;

struct edge{

    int first;

    int next;

    int to;

    int quan1,quan2;

}a[MAXN*];

int dis[MAXN],have[MAXN],node[MAXN];

queue<int> q;

int n,m,num,k,ans;

void cl(){

    memset(a,,sizeof(a));

    num=ans=;

}

void addedge(int from,int to,int quan1,int quan2){

    a[++num].to=to;

    a[num].quan1=quan1,a[num].quan2=quan2;

    a[num].next=a[from].first;

    a[from].first=num;

}

void spfa(){

    memset(dis,,sizeof(dis));

    memset(node,,sizeof(node));

    memset(have,,sizeof(have));

    dis[]=node[]=,have[]=;

    q.push();

    while(!q.empty()){

        int now=q.front();

        q.pop();

        have[now]=;

        for(int i=a[now].first;i;i=a[i].next){

            int to=a[i].to,quan=a[i].quan1,quan2=a[i].quan2;

            if(dis[to]>dis[now]+quan){

                dis[to]=dis[now]+quan,node[to]=quan2;

                if(!have[to]){

                    have[to]=;

                    q.push(to);

                }

            }

            else if(dis[to]==dis[now]+quan&&node[to]>quan2) node[to]=quan2;

        }

    }

}

int main()

{

    while(){

        scanf("%d%d",&n,&m);

        if(!n&&!m) break;

        cl();

        for(int i=;i<=m;i++){

            int x,y,z,d;

            scanf("%d%d%d%d",&x,&y,&z,&d);

            addedge(x,y,z,d),addedge(y,x,z,d);

        }

        spfa();

        for(int i=;i<=n;i++) ans+=node[i];

        printf("%d\n",ans);

    }

    return ;

}

巴特西

Road Construction

Input

Output

Sample Input

Output for the Sample Input

最新文章

热门文章