题目链接：

题解：

用dijkstra跑单元最短路径，如果对于顶点v，存在一系列边(ui，v)使得dis[v]最小(dis[v]表示0到v的距离)。这些边能且只能选一条，那么我们自然应该选cost最小的那个边了。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 9 typedef long long LL; 10 const int maxn = 1e5 + 10; 11 12 struct Edge { 13 int ne, u, v, c, d; 14 Edge(int ne, int u, int v, int d, int c) :ne(ne), u(u), v(v), d(d), c(c) {} 15 Edge() {} 16 }egs[maxn * 2]; 17 18 struct Heap { 19 int u, d, c; 20 Heap(int u, int d) :u(u), d(d) {} 21 Heap() {} 22 bool operator < (const Heap& tmp) const { 23 return d>tmp.d; 24 } 25 }; 26 27 struct Node { 28 int u, v, w; 29 bool operator < (const Node& tmp) const { 30 return w
           
             pq; 57 dis[0] = 0; 58 pq.push(Heap(0, 0)); 59 while (!pq.empty()) { 60 Heap x = pq.top(); pq.pop(); 61 int u = x.u; 62 if (done[u]) continue; 63 done[u] = true; 64 int p = head[u]; 65 while (p != -1) { 66 Edge &e = egs[p]; 67 if (dis[e.v]>dis[u] + e.d) { 68 dis[e.v] = dis[u] + e.d; 69 pre[e.v] = e.c; 70 pq.push(Heap(e.v, dis[e.v])); 71 } 72 else if (dis[e.v] == dis[u] + e.d) { 73 //这里贪心选cost最小的边 74 if (pre[e.v]>e.c) 75 pre[e.v] = e.c; 76 } 77 p = e.ne; 78 } 79 } 80 ans_d = 0; ans_c = 0; 81 for (int i = 0; i