题意：国王本来有一个铺路计划，后来发现太贵了，决定删除计划中的某些边，但是有2个原则，1：所有的城市必须能达到。 2：城市与首都（1号城市）之间的最小距离不能变大。 并且在这2个原则下使得建路消耗最小。

题解：现在来分析一下，使得n个点联通至少需要n-1条路，然后因为求最小消耗，所以路最多也就只有n-1条，除了首都以外，每一个都市都对应着一条路，我们只需要在dijkstra求最短路的时候，每次更新最短路的距离就更新这个点所对应的边，最后每个城市的点对应的边就是符合要求的边，最后求和一下就是答案了。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 #define ll long long 8 typedef pair
          
            pll; 9 const int INF = 0x3f3f3f3f;10 const int N = 10000+5;11 struct Node12 {13 int nt, to, d, c;14 }Edge[N*4];15 int head[N], dis[N], pre[N];16 int cnt = 0, n, m;17 void add(int u, int v, int d, int c)18 {19 Edge[cnt].to = v;20 Edge[cnt].d = d;21 Edge[cnt].c = c;22 Edge[cnt].nt = head[u];23 head[u] = cnt++;24 }25 void dijkstra()26 {27 memset(dis, INF, sizeof(dis));28 dis[1] = 0;29 priority_queue
           
            , greater
            
              > q;30 q.push(pll(0,1));31 while(!q.empty())32 {33 int u = q.top().second, d = q.top().first;34 q.pop();35 if(dis[u] != d) continue;36 for(int i = head[u]; ~i; i = Edge[i].nt)37 {38 int v = Edge[i].to;39 if(dis[v] > dis[u] + Edge[i].d)40 {41 dis[v] = dis[u] + Edge[i].d;42 pre[v] = i;43 q.push(pll(dis[v],v));44 }45 else if(dis[v] == dis[u]+Edge[i].d && Edge[i].c < Edge[pre[v]].c)46 {47 pre[v] = i;48 q.push(pll(dis[v],v));49 }50 }51 }52 }53 int main()54 {55 ios::sync_with_stdio(false);56 cin.tie(0);57 cout.tie(0);58 while(cin >> n >> m, n+m)59 {60 memset(head, -1, sizeof(head));61 cnt = 0;62 int x, y, d, c;63 for(int i = 0; i < m; i++)64 {65 cin >> x >> y >> d >> c;66 add(x,y,d,c);67 add(y,x,d,c);68 }69 dijkstra();70 ll ans = 0;71 for(int i = 2; i <= n; i++)72 {73 ans += Edge[pre[i]].c;74 }75 cout << ans << endl;76 }77 return 0;78 }