点击查看代码
#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
const int N=1005,M=100005;struct Graph{int h[N],e[M],ne[M],idx,w[M];Graph(){memset(h,-1,sizeof h);idx=0;}void add(int a,int b,int c){e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;}
}g1,g2;
int n,m;
bool st[N];
int dist1[N],dist2[N];void dijkstra(Graph &g,int dist[])
{memset(dist,0x3f,sizeof(int)* N );memset(st,0,sizeof st);dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;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=g.h[ver];i!=-1;i=g.ne[i]){int j=g.e[i];if(dist[j]>dist[ver]+g.w[i]){dist[j]=dist[ver]+g.w[i];heap.push({dist[j],j});}}}
}int main()
{cin>>n>>m;for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;g1.add(u,v,w);g2.add(v,u,w);}dijkstra(g1, dist1);dijkstra(g2,dist2);long long ans=0;for(int i=2;i<=n;i++){ans+=dist1[i]+dist2[i];}cout<<ans<<endl;
}