Time Limit:8000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Submit Status Practice Aizu 2249admin管理员组文章数量:1602103
Description
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
u1v1d1c1
.
.
.
uMvMdMcM
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 isdi 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 <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
using namespace std;
#define MAXN 10001
#define INF 999999999
struct Edge
{
int u, v, next, d, c;
}edge[MAXN * 4];
int head[MAXN], e;
int n, m;
int total;
int dis[MAXN];
int cost[MAXN];
bool vis[MAXN];
void add(int u, int v, int d, int c)
{
edge[e].u = u;
edge[e].v = v;
edge[e].d = d;
edge[e].c = c;
edge[e].next = head[u];
head[u] = e++;
}
void init()
{
e = 0;
memset(head, -1, sizeof(head));
memset(vis, false, sizeof(vis));
}
queue <int> q;
void solve()
{
while (!q.empty())
{
q.pop();
}
for (int i = 0; i <= n; i++)
{
dis[i] = INF;
cost[i] = INF;
}
int cur, next, ans = 0;
q.push(1);
vis[1] = true;
dis[1] = 0;
cost[1] = 0;
while (!q.empty())
{
cur = q.front();
q.pop();
vis[cur] = false;
for (int i = head[cur]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if (dis[v] > dis[cur] + edge[i].d)
{
dis[v] = dis[cur] + edge[i].d;
cost[v] = edge[i].c;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
else if (dis[v] == dis[cur] + edge[i].d && cost[v] > edge[i].c)
{
cost[v] = edge[i].c;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
ans += cost[i];
}
cout << ans << endl;
}
void input()
{
int u, v, d, c;
while (cin >> n >> m)
{
total = 0;
if (!n && !m)
{
break;
}
init();
for (int i = 0; i < m; i++)
{
cin >> u >> v >> d >> c;
add(u, v, d, c);
add(v, u, d, c);
total += 2 * c;
}
solve();
}
}
int main()
{
std::ios::sync_with_stdio(false);
input();
return 0;
}
本文标签: AizuconstructionRoad
版权声明:本文标题:Aizu 2249 Road Construction 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728396833a1157108.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论