CCF201609-4 交通规划（100分）

问题链接：CCF201609试题。

问题描述：参见上文。

问题分析：这是一个最优化的问题，也是一个单源最短路径问题，所有要用Dijkstra算法。题目要求在“所有城市乘坐高速铁路到首都的最短路程和原来一样长”的前提下，计算出“最少要改造多少铁路”？

程序说明：图的表示主要有三种形式，一是邻接表，二是邻接矩阵，三是边列表。邻接矩阵对于结点多和边少的情况都不理想。程序中用邻接表存储图，即g[]，是一种动态的存储。数组dist[]中存储单源（首都，结点1）到各个结点（城市）的最短距离。优先队列q按照边的权值从小到大排队，便于计算最短路径。

对于n个结点的城市，要连通起来，最少有n-1条道路就够了。

数组cost[i]用于存储要到达结点i，并且满足单源最短路径的条件，需要改造的铁路的长度。这是使用Dijkstra算法解决本问题需要增加的。程序中的72行就是增加的逻辑。

另外一个问题，从单源出发到达某个结点，最短路径有两条以上，并且路径长度相等时，需要选一个代价小的。例如，测试实例中，结点1到4有两条路径，1-2-4和1-3-4，其距离都是7，边1-2和1-3是必选的，边2-4和3-4是可选的，由于边2-4的权为3，而边3-4的权为2，所以为了到达结点4选择小的权2。程序中，这个逻辑体现在75行。

提交后得100分的C++语言程序如下：

/* CCF201609-4 交通规划 */#include <iostream>#include <vector>#include <queue>using namespace std;//#define DEBUGconst int INT_MAX2 = ((unsigned int)(-1) >> 1);const int MAXN = 10000;// 边struct _edge {    int v, cost;    _edge(int v2, int c){v=v2; cost=c;}};// 结点struct _node {    int u, cost;    _node(){}    _node(int u2, int c){u=u2; cost=c;}    bool Operator<(const _node n) const {        return cost > n.cost;    }};vector<_edge> g[MAXN+1];PRiority_queue<_node> q;int dist[MAXN+1];int cost[MAXN+1];bool visited[MAXN+1];void dijkstra_add(int start, int n){    for(int i=0; i<=n; i++) {        dist[i] = INT_MAX2;        cost[i] = INT_MAX2;        visited[i] = false;    }    dist[start] = 0;    cost[start] = 0;    q.push(_node(start, 0));    _node f;    while(!q.empty()) {        f = q.top();        q.pop();        int u = f.u;        if(!visited[u]) {            visited[u] = true;            int len = g[u].size();            for(int i=0; i<len; i++) {                int v2 = g[u][i].v;                if(visited[v2])                    continue;                int tempcost = g[u][i].cost;                int nextdist = dist[u] + tempcost;                if(dist[v2] > nextdist) {                    dist[v2] = nextdist;                    cost[v2] = tempcost;                      // add code                    q.push(_node(v2, dist[v2]));                } else if(dist[v2] == nextdist)                    cost[v2] = min(cost[v2], tempcost); // add code            }        }    }}int main(){    int n, m, src, dest, cost2;    // 输入数据，构建图    cin >> n >> m;    for(int i=1; i<=m; i++) {        cin >> src >> dest >> cost2;        g[src].push_back(_edge(dest, cost2));        g[dest].push_back(_edge(src, cost2));    }    // 改进的Dijkstra算法    dijkstra_add(1, n);#ifdef DEBUG    cout << "dist : ";    for(int i=1; i<=n; i++)        cout << dist[i] << " ";    cout << endl;    cout << "cost : ";    for(int i=1; i<=n; i++)        cout << cost[i] << " ";    cout << endl;#endif    // 统计边的权重    int ans=0;    for(int i=2; i<=n; i++)        ans += cost[i];    cout << ans << endl;    return 0;}