AOJ 2249 - Road Construction

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2249

Problem H: 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.

Sample Input

3 3
1 2 1 2
2 3 2 1
3 1 3 2

Output for the Sample Input

3

http://www.hankcs.com/program/cpp/aoj-2249-road-construction.html
修路：ACM之王要在全国改造交通网络，第一保证首都最短路，第二保证最低花费。

2.5 它们其实都是“图”

最短路 dijkstra 

ACM-ICPC Japan的一道题，dijkstra 条件复杂化变种而已。先满足最短路，然后再满足最低花费。

// first 当前最短路径长度，second当前顶点编号

typedef pair<int, int> P;

// 图

vector<edge> G[MAX_V];

// 最短距离

int d[MAX_V];

// V是顶点数

int V;

// 求解从顶点s出发到所有点的最短距离（并非最小花费）

void dijkstra(int s)

{

    priority_queue<P, vector<P>, greater<P> > que;

    memset(d, 0x3f, sizeof(d));

    d[s] = 0;

    que.push(P(0, s));

 

    while (!que.empty())

    {

        P p = que.top(); que.pop();

        int v = p.second;

        if (d[v] < p.first) continue;

        for (int i = 0; i < G[v].size(); ++i)

        {

            edge e = G[v][i];

            if (d[e.to] > d[v] + e.distance)

            {

                d[e.to] = d[v] + e.distance;

                que.push(P(d[e.to], e.to));

            }

        }

    }

}

int main(int argc, char *argv[])

{

 

    int /*N = V,*/ M;

    while (cin >> V >> M && V)

    {

        for (int i = 0; i < V; ++i)

        {

            G[i].clear();

        }

        for (int i = 0; i < M; ++i)

        {

            int u, v, d, c;

            cin >> u >> v >> d >> c;

            --u, --v;

            G[u].push_back(edge(v, d, c));

            G[v].push_back(edge(u, d, c));

        }

        // 首都是0号

          dijkstra(0);

        int ans = 0;

        for (int i = 1; i < V; ++i)

        {

            int min_cost = 0x3f3f3f3f;

            // 找寻满足优先距离最短，然后费用最低的那个最低费用

            for (int j = 0; j < G[i].size(); ++j)

            {

                if (d[G[i][j].to] + G[i][j].distance == d[i] && G[i][j].cost < min_cost)

                {

                    min_cost = G[i][j].cost;

                }

            }

            ans += min_cost;

        }

        cout << ans << endl;

    }

 

    return 0;

}

感觉有点别扭，主要是“找寻满足优先距离最短，然后费用最低的那个最低费用”的那个循环完全就是在模拟，感觉技术含量太低了。既然用了dijkstra，那就把它用到极致吧！

// 从顶点from指向顶点to的权值为cost的边

typedef struct edge

{

    int to, distance, cost;

    edge(){}

    edge(int to, int distance, int cost) : to(to), distance(distance), cost(cost){}

    bool operator > (const edge & b) const

    {

        return distance != b.distance ? distance > b.distance : cost > b.cost;

    }

} P;

// first 最短路径，second顶点编号

// 图

vector<edge> G[MAX_V];

// V是顶点数

int V;

bool visited[MAX_V];

// 求解从顶点s出发到所有点的最短花费

int dijkstra(int s)

{

    int result = 0;

    priority_queue<P, vector<P>, greater<P> > que;

    memset(visited, 0, V * sizeof(bool));

    que.push(P(0, 0, 0));

 

    while (!que.empty())

    {

        P p = que.top(); que.pop();

        int v = p.to;

        if (visited[v]) continue;

        visited[v] = true;

        result += p.cost;

        for (int i = 0; i < G[v].size(); ++i)

        {

            edge e = G[v][i];

            que.push(P(G[v][i].to, p.distance + G[v][i].distance, G[v][i].cost));

        }

    }

 

    return result;

}

int main(int argc, char *argv[])

{

    int /*N = V,*/ M;

    while (cin >> V >> M && V)

    {

        for (int i = 0; i < V; ++i)

        {

            G[i].clear();

        }

        for (int i = 0; i < M; ++i)

        {

            int u, v, d, c;

            cin >> u >> v >> d >> c;

            --u, --v;

            G[u].push_back(edge(v, d, c));

            G[v].push_back(edge(u, d, c));

        }

 

        cout << dijkstra(0) << endl;

    }

    return 0;

}

Read full article from AIZU ONLINE JUDGE