点击查看代码
#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
const int N=1005,M=100005;
int h1[N],e1[M],idx1,ne1[M],w1[M];
int h2[N],e2[M],idx2,ne2[M],w2[M];
int dist1[N],dist2[N];
int n,m;
bool st[N];void add(int a,int b,int c,int h[],int e[],int& idx,int ne[],int w[])
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}void dijkstra(int h[],int e[],int idx,int ne[],int w[],int dist[])
{for(int i=1;i<=n;i++) dist[i]=0x3f3f3f3f;memset(st,0,sizeof st);priority_queue<PII,vector<PII>,greater<PII>> heap;dist[1]=0;heap.push({dist[1],1});while(!heap.empty()){auto t=heap.top();heap.pop();int ver=t.second;if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[ver]+w[i]){dist[j]=dist[ver]+w[i];heap.push({dist[j],j});}}}
}int main()
{ios::sync_with_stdio(0),cin.tie(0);memset(h1,-1,sizeof h1);memset(h2,-1,sizeof h2);cin>>n>>m;for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w,h1,e1,idx1,ne1,w1);add(v,u,w,h2,e2,idx2,ne2,w2);}dijkstra(h1,e1,idx1,ne1,w1,dist1);dijkstra(h2,e2,idx2,ne2,w2,dist2);long long ans=0;for(int i=2;i<=n;i++){ans+=dist1[i]+dist2[i];}cout<<ans<<endl;}