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

题目大意

某国王需要修路,王国有一个首都和多个城市,需要修路。已经有修路计划了,但是修路费用太高。

为了减少修路费用,国王决定从计划中去掉一些路,但是需要满足一下两点:

  1. 保证所有城市都能连通
  2. 所有城市到首都的最短路不变

思路

首先看题目的时候以为是最小生成树,原计划已经满足第一点(否则去掉边也不满足),只要按费用生成即可,然后发现不对劲,还要考虑城市之间的距离。

既然是最短路然后考虑用$Dijkstra$,刚开始是先把所有费用求出来,然后减去去掉边的费用,在$Dijkstra$改啊改,实在没改出来= =,要考虑距离和最小费用。。

翻题解,思路是顺着来的,在$Dijkstra$找最短路的时候,就记录一下费用:

if(d[e.to] > d[v] + e.dist) {
    ...
    prev_min_cost[e.to] = e.cost; // 最短路必经之路,则费用也必须要
}
else if(d[e.to] == d[v] + e.dist) // 最短路可选择之路,选择最小的费用连接
    prev_min_cost[e.to] = min(prev_min_cost[e.to], e.cost);
// else if(d[e.to] < d[v] + e.dist) // 已经不是最短路了= =无视掉费用

AC代码

/*************************************************************************
    > File Name: 2249.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-11-14 六 09:47:56 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

struct edge {
    int to, dist, cost;
    edge(int to, int dist, int cost) : to(to), dist(dist), cost(cost) {}
    bool operator<(const edge &b) const{
        return dist > b.dist;
    }
};
vector<edge> G[10005];
int N, M; // 节点数,道路数
int d[10005]; // 距离源点s(s==1)的最小距离
int prev_min_cost[10005]; // 前面节点的最小花费
int ans;

void dijkstra(int s) {
    memset(d, 0x3f, sizeof(d));
    memset(prev_min_cost, 0x3f, sizeof(prev_min_cost));
    d[s] = 0;
    priority_queue<edge> que;
    que.push(edge(s, d[s], 0));
    while(!que.empty()) {
        edge p = que.top(); que.pop();
        int v = p.to;
        if(d[v] < p.dist) continue;
        for(int i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.dist) {
                d[e.to] = d[v] + e.dist;
                que.push(edge(e.to, d[e.to], G[v][i].cost));
                prev_min_cost[e.to] = e.cost; // 最短路必经之路,则费用也必须要
            }
            else if(d[e.to] == d[v] + e.dist) // 最短路可选择之路,选择最小的费用连接
                prev_min_cost[e.to] = min(prev_min_cost[e.to], e.cost);
        }
    }
}

void solve() {
    dijkstra(1);
    for(int u=2; u<=N; ++u) ans+=prev_min_cost[u]; // 求出所有必须的费用
    cout << ans << endl;

}

int main()
{
#ifdef Oj
    freopen("2249.in", "r", stdin);
#endif
    cin.sync_with_stdio(false);
    int u,v,d,c;
    while(cin >> N >> M) {
        for(int u=1; u<=N; ++u) G[u].clear();
        ans = 0;
        if(N == M && N == 0) break;
        for(int i=0; i<M; ++i) {
            cin >> u >> v >> d >> c;
            G[u].push_back(edge(v, d, c)); // 构图
            G[v].push_back(edge(u, d, c));
        }

        solve();
    }
    return 0;
}