[Aizu2249] Road Construction

题意：给你一个图，要你按C值构出最小生成树，但要保证1到所有点的最短距离不变

题解：

spfa+最小生成树

每个点都会被唯一与之对应的一条边松弛

跑一遍spfa，找出所有最短路要经过的边，构最小生成树的时候先选这些边，然后再按C值从小到大加边

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #define ll long long
 9 using namespace std;
10 
11 const int N = 10010;
12 const int M = 20010;
13 
14 int n,m,e_num,ans,k;
15 int nxt[M*2],to[M*2],w[M*2],h[N],dis[N],fa[N],pre[N],bl[M*2],val[M*2];
16 bool in[N];
17 
18 struct Node {
19   int x,y,z,c,f;
20   bool operator < (const Node &a) const {
21     return f==a.f?c<a.c:f>a.f;
22   }
23 }e[M];
24 
25 queue<int> q;
26 
27 int gi() {
28   int x=0,o=1; char ch=getchar();
29   while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
30   if(ch=='-') o=-1,ch=getchar();
31   while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
32   return o*x;
33 }
34 
35 void add(int x, int y, int z, int c, int id) {
36   nxt[++e_num]=h[x],to[e_num]=y,w[e_num]=z,bl[e_num]=id,val[e_num]=c,h[x]=e_num;
37 }
38 
39 void spfa() {
40   memset(dis,63,sizeof(dis));
41   dis[1]=0,in[1]=1,q.push(1);
42   while(!q.empty()) {
43     int u=q.front();
44     in[u]=0,q.pop();
45     for(int i=h[u]; i; i=nxt[i]) {
46       int v=to[i];
47       if(dis[u]+w[i]<dis[v]) {
48     pre[v]=i;
49     dis[v]=dis[u]+w[i];
50     if(!in[v]) in[v]=1,q.push(v);
51       }
52       else if(dis[u]+w[i]==dis[v]) {
53     if(val[i]<val[pre[v]]) pre[v]=i;
54       }
55     }
56   }
57 }
58 
59 int find(int x) {
60   return x==fa[x]?x:fa[x]=find(fa[x]);
61 }
62 
63 void init() {
64   e_num=ans=k=0;
65   memset(h,0,sizeof(h));
66   memset(pre,0,sizeof(pre));
67 }
68 
69 int main() {
70   while(scanf("%d%d", &n, &m) && n+m) {
71     init();
72     for(int i=1; i<=m; i++) {
73       int x=gi(),y=gi(),z=gi(),c=gi();
74       add(x,y,z,c,i),add(y,x,z,c,i);
75       e[i]=(Node){x,y,z,c,0};
76     }
77     spfa();
78     for(int i=2; i<=n; i++) {
79       e[bl[pre[i]]].f=1;
80     }
81     sort(e+1,e+m+1);
82     for(int i=1; i<=n; i++) fa[i]=i;
83     for(int i=1; i<=m; i++) {
84       int x=e[i].x,y=e[i].y;
85       int xx=find(x),yy=find(y);
86       if(xx==yy) continue;
87       ans+=e[i].c,fa[yy]=xx,k++;
88       if(k==n-1) break;
89     }
90     printf("%d
", ans);
91   }
92   return 0;
93 }