算法1

最短路和最小生成树结合

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=5e5+5;
typedef pair<int,int>PLL;
struct edge{
    int x,dis;
    bool operator < (const edge &e)const{
        return dis>e.dis;
    }
};
vector<edge>g[maxn];
const int INF=0x3f3f3f3f;
int n,m;
int vis[maxn];
int dis[maxn],pre[maxn];
int ans;
void dijkstra(){
    memset(dis,INF,sizeof(dis));
    memset(pre,INF,sizeof(pre));
    priority_queue<edge>q;
    q.push({1,0});
    dis[1]=0;
    //pre[1]=0;
    while(!q.empty()){
        auto t=q.top();
        q.pop();
        int x=t.x;
        int y=t.dis;
        if(vis[x]){
            continue;
        }
        vis[x]=1;
        for(int i=0;i<g[x].size();i++){
            int e=g[x][i].x;
            int dist=g[x][i].dis;
            if(vis[e]==0){
                if(dis[e]>y+dist){
                    dis[e]=y+dist;
                    pre[e]=dist;
                    q.push({e,dis[e]});
                }else if(dis[e]==y+dist){
                    pre[e]=min(pre[e],dist);
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    dijkstra();
    for(int i=2;i<=n;i++){
        //printf("%d %d\n",dis[i],pre[i]);
        ans+=pre[i];
    }
    printf("%d\n",ans);
    return 0;
}