最短路(Dijkstra) HDOJ 4318 Power transmission-白红宇

最短路(Dijkstra) HDOJ 4318 Power transmission

阅读量：6815 次

发布时间：2019-06-26

本文共 1778 字，大约阅读时间需要 5 分钟。

题意：起点s到终点t送电，中途会有损耗，问最小损耗是多少

分析：可以转换为单源最短路问题，用优先队列的Dijkstra版本，d[]表示从s出发到当前点的最小损耗，用res保存剩下的电量。当到达t就结束，因为按照w从小到大排序，访问过的点都已经最优，这是贪心思想

收获：复习了Dijkstra，进一步理解Dijkstra的贪心的思想(程序跑得慢，还可优化)

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-8-24 9:51:51* File Name     :I.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;typedef pair
                      
                        P;const int N = 5e4 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;struct Edge { int v; double w, res; bool operator < (const Edge &r) const { return w > r.w; }};vector
                       
                         G[N];bool vis[N];double d[N];int n, s, t;double M;void Dijkstra(void) { priority_queue
                        
                          Q; memset (vis, false, sizeof (vis)); for (int i=1; i<=n; ++i) d[i] = INF; d[s] = 0; Q.push ((Edge) {s, 0, M}); while (!Q.empty ()) { Edge r = Q.top (); Q.pop (); int u = r.v; double res = r.res; if (vis[u]) continue; vis[u] = true; if (u == t) { printf ("%.2f\n", M - res); return ; } for (int i=0; i
                         
                           d[u] + res * w) { d[v] = d[u] + res * w; Q.push ((Edge) {v, d[v], res - res * w}); } } } puts ("IMPOSSIBLE!");}int main(void) { while (scanf ("%d", &n) == 1) { for (int i=1; i<=n; ++i) { G[i].clear (); int k; scanf ("%d", &k); for (int j=1; j<=k; ++j) { int v; double w; scanf ("%d%lf", &v, &w); w /= 100; G[i].push_back ((Edge) {v, w}); } } scanf ("%d%d%lf", &s, &t, &M); Dijkstra (); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4754749.html

你可能感兴趣的文章