CCF 交通规划(最短路加边权维护)

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<stack> #include<set> using namespace std; typedef long long ll; const int maxn=300010; const int N=10010; int n,m; struct node{ int v,val; node(int vv,int vall){ v=vv,val=vall; } friend bool operator<(const node &a,const node &b){ return a.val > b.val; } }; priority_queue<node> que; struct edge{ int to,val; edge(int too,int vall){ to=too,val=vall; } }; vector<edge> vec[100010]; int dis[N]; int vis[N]; int f[N]; void dij(){ int i; que.push(node(1,0)); int v; for(i=1;i<=n;++i){ dis[i]=0xfffffff; f[i]=0xfffffff; } dis[1]=0; f[1]=0; while(!que.empty()){ v=que.top().v; que.pop(); if(vis[v]) continue; vis[v]=true; for(i=0;i<vec[v].size();++i){ if(!vis[vec[v][i].to]&&dis[vec[v][i].to]>=dis[v]+vec[v][i].val){ dis[vec[v][i].to]=dis[v]+vec[v][i].val; f[vec[v][i].to]=min(f[vec[v][i].to],vec[v][i].val); que.push(node(vec[v][i].to,dis[vec[v][i].to])); } } } } int main(){ scanf("%d%d",&n,&m); int i; int u,v,l; for(i=0;i<m;++i){ scanf("%d%d%d",&u,&v,&l); vec[u].push_back(edge(v,l)); vec[v].push_back(edge(u,l)); } dij(); int ans=0; for(i=1;i<=n;++i){ ans+=f[i]; } cout<<ans<<endl; return 0; }