【最短路】速度限制

winston · 发表于 2012-2-3 13:16:00

【问题描述】在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。两地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：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <bitset>
#include <cmath>
using std::bitset;
const char fi[] = "speed.in";
const char fo[] = "speed.out";
const int maxN = 210;
const int SIZE = 1050000;
const int MOD = (1 << 20) - 1;
const int MAX_int = 0x3fffff00;
const int MIN_int = -MAX_int;
const double MAX_double = 1e198;
const double MIN_double = -MAX_double;
const double zero = 1e-12;
struct Edge
{int dest, _d, _v; Edge *next; };
struct Que
{
int Last, ths, _v;
Que(int la, int th, int v)
{Last = la; ths = th; _v = v; }
Que() {Last = ths = _v = 0; }
};
Edge *edge[maxN];
double dist[maxN][maxN];
Que q[SIZE];
bitset <maxN> marked[maxN];
int pre[maxN][maxN];
int n, m, start, finish, f, r;
void init_file()
{
freopen(fi, "r", stdin);
freopen(fo, "w", stdout);
}
inline void insert(int u,
int v, int _d, int _v)
{
Edge *p = new Edge;
p -> dest = v;
p -> _d = _d;
p -> _v = _v;
p -> next = edge[u];
edge[u] = p;
}
void readdata()
{
scanf("%d%d%d", &n, &m, &finish);
for (int i = 0; i < m; ++i)
{
int u, v, _d, _v;
scanf("%d%d%d%d", &u, &v, &_v, &_d);
insert(u, v, _d, _v);
}
}
inline void Enq(int Last, int ths, int _v)
{
marked[Last].set(ths);
++r;
r &= MOD;
q[r] = Que(Last, ths, _v);
}
inline Que Deq()
{
++f;
f &= MOD;
marked[q[f].Last].reset(q[f].ths);
return q[f];
}
void Spfa()
{
while (f != r)
{
Que Now = Deq();
int ths = Now.ths;
int _v = Now._v;
int Last = Now.Last;
for (Edge *p = edge[ths]; p; p = p -> next)
{
if (p -> _v) _v = p -> _v;
double t = p -> _d / (double)_v;
if (dist[Last][ths] + t < dist[ths][p -> dest])
{
dist[ths][p -> dest] = dist[Last][ths] + t;
pre[ths][p -> dest] = Last;
if (!marked[ths].test(p -> dest))
Enq(ths, p -> dest, _v);
}
_v = Now._v; //要記住每次還原速度。
}
}
}
void print(int Last, int ths)
{
if (ths == 0) return;
print(pre[Last][ths], Last);
printf("%d ", Last);
}
void work()
{
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
dist[i][j] = MAX_double;
dist[0][start] = 0;
Enq(0, start, 70);
Spfa();
double Min = MAX_double;
for (int i = 0; i < n; ++i)
Min = std::min(Min, dist[i][finish]);
for (int i = 0; i < n; ++i)
if (fabs(Min - dist[i][finish]) < zero)
{print(i, finish); break; }
printf("%d", finish);
}
int main()
{
init_file();
readdata();
work();
exit(0);
}

复制代码

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

		自动登录	找回密码
密码			用户注册