【最短路】速度限制

winston

【问题描述】    在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。    你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。两地A和B，最多只有一条道路从A连接到B。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然，你的车速不能超过当前的速度限制。【输入】    输入文件speed.in的第一行是3个整数N，M和D(2<＝N<=150)，表示道路的数目，用0..N-1标记。M是道路的总数，D表示你的目的地。接下来的M行，每行描述一条道路，每行有4个整数A(0≤A<N)，B(0≤B<N)，V(0≤V≤500)and L(1≤L≤500)，这条路是从A到B的，速度限制是V，长度为L。如果V是0，表示这条路的限速未知。如果V不为0，则经过该路的时间T=L/V。否则T=L/Vold，Vold是你到达该路口前的速度。开始时你位于0点，并且速度为70。【输出】        输出文件speed.out仅一行整数，表示从0到D经过的城市。        输出的顺序必须按照你经过这些城市的顺序，以0开始，以D结束。仅有一条最快路线。【样例】speed.in6 15 10 1 25 680 2 30 500 5 0 1011 2 70 771 3 35 422 0 0 222 1 40 862 3 0 232 4 45 403 1 64 143 5 0 234 1 95 85 1 0 845 2 90 645 3 36 40speed.out0 5 2 3 1拆點+SPFA。

普通的SPFA中，用dist數組保存臨時最短距離，並用標誌數組保存是否在隊列中。

而此題，當前點臨時最短距離（即題目中的最短時間），還與從上一個來的初速度有關，所以將dist多加一個參數即前一個點的編號，並且在隊列中要記錄走過當前這條邊的速度。
Accode：

4. #include <cstdio>
5. #include <cstring>
6. #include <cstdlib>
7. #include <bitset>
8. #include <cmath>
9. using std::bitset;
11. const char fi[] = "speed.in";
12. const char fo[] = "speed.out";
13. const int maxN = 210;
14. const int SIZE = 1050000;
15. const int MOD = (1 << 20) - 1;
16. const int MAX_int = 0x3fffff00;
17. const int MIN_int = -MAX_int;
18. const double MAX_double = 1e198;
19. const double MIN_double = -MAX_double;
20. const double zero = 1e-12;
22. struct Edge
23.   {int dest, _d, _v; Edge *next; };
25. struct Que
26. {
27.   int Last, ths, _v;
28.   Que(int la, int th, int v)
29.     {Last = la; ths = th; _v = v; }
30.   Que() {Last = ths = _v = 0; }
31. };
33. Edge *edge[maxN];
34. double dist[maxN][maxN];
35. Que q[SIZE];
36. bitset <maxN> marked[maxN];
37. int pre[maxN][maxN];
38. int n, m, start, finish, f, r;
40.   void init_file()
41.   {
42.     freopen(fi, "r", stdin);
43.     freopen(fo, "w", stdout);
44.   }
46.   inline void insert(int u,
47.     int v, int _d, int _v)
48.   {
49.     Edge *p = new Edge;
50.     p -> dest = v;
51.     p -> _d = _d;
52.     p -> _v = _v;
53.     p -> next = edge[u];
54.     edge[u] = p;
55.   }
57.   void readdata()
58.   {
59.     scanf("%d%d%d", &n, &m, &finish);
60.     for (int i = 0; i < m; ++i)
61.     {
62.       int u, v, _d, _v;
63.       scanf("%d%d%d%d", &u, &v, &_v, &_d);
64.       insert(u, v, _d, _v);
65.     }
66.   }
68.   inline void Enq(int Last, int ths, int _v)
69.   {
70.     marked[Last].set(ths);
71.     ++r;
72.     r &= MOD;
73.     q[r] = Que(Last, ths, _v);
74.   }
76.   inline Que Deq()
77.   {
78.     ++f;
79.     f &= MOD;
80.     marked[q[f].Last].reset(q[f].ths);
81.     return q[f];
82.   }
84.   void Spfa()
85.   {
86.     while (f != r)
87.     {
88.       Que Now = Deq();
89.       int ths = Now.ths;
90.       int _v = Now._v;
91.       int Last = Now.Last;
92.       for (Edge *p = edge[ths]; p; p = p -> next)
93.       {
94.         if (p -> _v) _v = p -> _v;
95.         double t = p -> _d / (double)_v;
96.         if (dist[Last][ths] + t < dist[ths][p -> dest])
97.         {
98.           dist[ths][p -> dest] = dist[Last][ths] + t;
99.           pre[ths][p -> dest] = Last;
100.           if (!marked[ths].test(p -> dest))
101.             Enq(ths, p -> dest, _v);
102.         }
103.         _v = Now._v; //要記住每次還原速度。
104.       }
105.     }
106.   }
108.   void print(int Last, int ths)
109.   {
110.     if (ths == 0) return;
111.     print(pre[Last][ths], Last);
112.     printf("%d ", Last);
113.   }
115.   void work()
116.   {
117.     for (int i = 0; i < n; ++i)
118.      for (int j = 0; j < n; ++j)
119.       dist[i][j] = MAX_double;
120.     dist[0][start] = 0;
121.     Enq(0, start, 70);
122.     Spfa();
123.     double Min = MAX_double;
124.     for (int i = 0; i < n; ++i)
125.       Min = std::min(Min, dist[i][finish]);
126.     for (int i = 0; i < n; ++i)
127.      if (fabs(Min - dist[i][finish]) < zero)
128.       {print(i, finish); break; }
129.     printf("%d", finish);
130.   }
132. int main()
133. {
134.   init_file();
135.   readdata();
136.   work();
137.   exit(0);
138. }

复制代码

作者：Whjpji 发表于2012-2-3 9:58:55 原文链接