spfa+dik

``` #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define int long long using namespace std; const int inf=0x3f3f3f3f; const int maxn=1e6+5; struct EDG { int u,v,next,w; }edge[maxn]; int head[maxn],vis[maxn],index,n,m,s; int dist[maxn]; void add(int u,int v,int w) { edge[index].v=v; edge[index].next=head[u]; edge[index].w=w; head[u]=index++; } void spfa(int s) { queue <int> q; for(int i=1;i<=n;i++) dist[i]=1e18; memset(vis,0,sizeof(vis)); q.push(s); dist[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(dist[v]>dist[u]+edge[i].w) { dist[v]=dist[u]+edge[i].w; if(!vis[v]) { vis[v]=true; q.push(v); } } } } } void solve(int s) { int k; int ans=0; for(int i=1;i<=n;i++) { if(i==s) continue; int t=inf; for(int j=head[i];~j;j=edge[j].next) { int v=edge[j].v; if(dist[v]+edge[j].w==dist[i]) { if(edge[j].w<t) { t=edge[j].w; } } } ans+=t; } cout<<ans; } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); cin>>n>>m; for(int i=0;i<=n;i++) head[i]=-1; for(int i=0;i<m;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } scanf("%d",&s); spfa(s); solve(s); return 0; } ```