Aizu-2249 Road Construction（dijkstra求最短路）

Aizu - 2249

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

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

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<functional>

 using namespace std;

 #define ll long long

 typedef pair<int, int> pll;

 const int INF = 0x3f3f3f3f;

 const int N = +;

 struct Node

 {

     int nt, to, d, c;

 }Edge[N*];

 int head[N], dis[N], pre[N];

 int cnt = , n, m;

 void add(int u, int v, int d, int c)

 {

     Edge[cnt].to = v;

     Edge[cnt].d = d;

     Edge[cnt].c = c;

     Edge[cnt].nt = head[u];

     head[u] = cnt++;

 }

 void dijkstra()

 {

     memset(dis, INF, sizeof(dis));

     dis[] = ;

     priority_queue<pll, vector<pll>, greater<pll> > q;

     q.push(pll(,));

     while(!q.empty())

     {

         int u = q.top().second, d = q.top().first;

         q.pop();

         if(dis[u] != d) continue;

         for(int i = head[u]; ~i; i = Edge[i].nt)

         {

             int v = Edge[i].to;

             if(dis[v] > dis[u] + Edge[i].d)

             {

                 dis[v] = dis[u] + Edge[i].d;

                 pre[v] = i;

                 q.push(pll(dis[v],v));

             }

             else if(dis[v] == dis[u]+Edge[i].d && Edge[i].c < Edge[pre[v]].c)

             {

                 pre[v] = i;

                 q.push(pll(dis[v],v));

             }

         }

     }

 }

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     cout.tie();

     while(cin >> n >> m, n+m)

     {

         memset(head, -, sizeof(head));

         cnt = ;

         int x, y, d, c;

         for(int i = ; i < m; i++)

         {

             cin >> x >> y >> d >> c;

             add(x,y,d,c);

             add(y,x,d,c);

         }

         dijkstra();

         ll ans = ;

         for(int i = ; i <= n; i++)

         {

             ans += Edge[pre[i]].c;

         }

         cout << ans << endl;

     }

     return ;

 }