[图论训练]BZOJ 3245: 最快路线【最短路】

Description

精明的小R每每开车出行总是喜欢走最快路线,而不是最短路线.很明显,每条道路的限速是小R需要考虑的关键问题.不过有一些限速标志丢失了,于是小R将不知道能开多快.不过有一个合理的方法是进入这段道路时不改变速度行驶.你的任务就是计算从小R家(0号路口)到D号路口的最快路线.

现在你得到了这个城市的地图,这个地图上的路都是单向的,而且对于两个路口A和B,最多只有一条道路从A到B.并且假设可以瞬间完成路口的转弯和加速.

Input

第一行是三个整数N,M,D(路口数目,道路数目,和目的地). 路口由0...N-1标号

接下来M行，每行描述一条道路:有四个整数A,B,V,L,(起始路口,到达路口,限速,长度) 如果V=0说明这段路的限速标志丢失.

开始时你位于0号路口,速度为70.

Output

仅仅一行,按顺序输出从0到D经过的城市.保证最快路线只有一条.

Sample Input

6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40

Sample Output

0 5 2 3 1

HINT

【数据范围】

30% N<=20

100% 2<=N<=150;0<=V<=500;1<=L<=500

Source

Spfa

思路：其实很明显的，这里不仅要记录到这个点的时间，还有到这个点的速度，于是记录一个二维的dist[x][y]表示到x点时速度为y最短时间即可

需要注意的是为了使到这个点的速度最小，可能经过一个点多次，所以输出路径的数组需要开大，此外这个最大值比较大

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#define maxn 100000
using namespace std;
int head[maxn],nex[maxn],point[maxn],len[maxn],speed[maxn], now;
typedef pair<int, int> pii;
pii pre[500][540];
int visit[500][540];
double dist[500][540];
int ans[100000];
void add(int x,int y,int s,int l)
{
    nex[++now] = head[x];
    head[x] = now;
    point[now] = y;
    len[now] = l;
    speed[now] = s;
}
void spfa(int s)
{
    for(int i=0;i<=199;i++)
        for(int j = 0; j <= 539; j++)dist[i][j] = -1;
    dist[s][70] = 0;
    visit[s][70] = 1;
    queue<pii>q;
    q.push(make_pair(s, 70));
    while(!q.empty())
    {
        pii k = q.front();
        q.pop();
        visit[k.first][k.second] = 0;
        for(int i = head[k.first]; i; i = nex[i])
        {
            int u = point[i], sp;
            double di = 0;
            if(speed[i] != 0)
            {
                di = dist[k.first][k.second] + 1.0*len[i] / speed[i], sp = speed[i];
            }
            else
            {
                di = dist[k.first][k.second] + 1.0*len[i] / k.second, sp = k.second;
            }
            if(di < dist[u][sp] || dist[u][sp] == -1)
            {
                dist[u][sp] = di;
                pre[u][sp] = k;
                if(!visit[u][sp])
                {
                    visit[u][sp] = 1;
                    q.push(make_pair(u,sp));
                }
            }
        }
    }
}
int main()
{
    int n,m,d,x,y,a,b,h=0;
    scanf("%d%d%d",&n,&m,&d);
    d++;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%d%d",&x,&y,&a,&b);
        add(x + 1, y + 1, a, b);
    }
    spfa(1);
    double an = 1000000000.00;
    for(int i = 0; i <= 500; i++)if(dist[d][i] != -1)
    {
        if(dist[d][i] < an)
        {
            an = dist[d][i];
            y = i;
        }
    }
    x = d;
    ans[++h] = d;
    while(pre[x][y].first != 0 || pre[x][y].second != 0)
    {
        ans[++h] = pre[x][y].first;
        int xx = pre[x][y].first, yy = pre[x][y].second;
        x = xx; y = yy;
    }
    for(int i = h; i >= 2; i--)
    {
        printf("%d ",ans[i]-1);
    }
    printf("%d
",ans[1]-1);
    return 0;
}