201609-4 ccf 交通规划（dijstra（堆优化））

矫情吗；* 2022-05-14 12:28 128阅读 0赞

题目链接：  
[交通规划][Link 1]

题目大意：  
中文题，不解释！！！

解题思路：  
题目要求我们要满足到节点1的最短距离不变，还要使总的经过的路径长度最小。  
那么在保证最短路径不变的情况下，如何保证经过路径长度最小呢？

由案例可知道，只有当某个节点有多条路到节点1的最短路都一样长时，才会使答案会有不同。  
那么要使经过的总路径最短，换一个想法，是不是就是使得重复走的路径最大呢？比如案例中5比4大，所以选择重复走5。  
所以我们需要记录对节点v实现松弛操作的u–v的路的长度，如果之后我们继续松弛到节点v,发现最短路径一样，我们只需要判断一下当前的路的长度是否比之前记录的小，如果是那么选择走当前的路。为什么呢？？因为当前路径小的，而最短路径又一样，重复走的路径就比较大（证明：dijstra算法用来松弛的u已经是最短路径，那么对于1–>u是必须要走的),最终总路径就越小。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <vector>
    
    using namespace std;
    const int MAXN = 1e4+233;
    const int INF = 0x3f3f3f;
    int n,m,ans;
    
    int vis[MAXN],dist[MAXN],pre[MAXN],f[MAXN];
    
    struct node{
        int v;
        int c;
        node(int _v, int _c):v(_v),c(_c){}
        bool operator <(const node &a)const{
            return c > a.c;
        }
    };
    
    vector<node> g[MAXN];
    
    
    void dijstra(){
        priority_queue<node> pq;
        pq.push(node(1,0));
        while(!pq.empty()){
            node tmp = pq.top();
            pq.pop();
            int u = tmp.v;
            if(vis[u]) continue;
            vis[u] = 1;
            ans += (dist[u] - dist[f[u]]);  //这里需要注意，要减去之前的那段重复路径
            for(int i =0; i<g[u].size(); ++i){
                int v = g[u][i].v;
                if(!vis[v]){
                    if(dist[v] > tmp.c + g[u][i].c) {
                        dist[v] = tmp.c + g[u][i].c;
                        pre[v] = g[u][i].c;
                        f[v] = u;
                        pq.push(node(v,dist[v]));
                    }else if(dist[v] == tmp.c + g[u][i].c){
                        if(g[u][i].c < pre[v]){
                            f[v] = u;
                            pre[v] = g[u][i].c;
                        }
                    }
                }
            }
        }
    }
    
    void init(){
        memset(vis, 0, sizeof(vis));
        memset(f, 0, sizeof(f));
        for(int i=2; i<MAXN; ++i)  dist[i] = INF;
        memset(pre, 0, sizeof(pre));
        for(int i=0; i<MAXN; ++i) g[i].clear();
        dist[0] = dist[1] = ans = 0;
    }
    
    int main(){
        init();
        cin>>n>>m;
        for(int i=0; i<m; ++i){
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            g[u].push_back(node(v,c));
            g[v].push_back(node(u,c));
        }
    
        dijstra();
        cout<<ans<<endl;
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T44