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
直接二维SPFA。。。没啥好讲的
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1e9
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1; char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=1.5e2,V=5e2;
int pre[N*N+10],now[N+10],child[N*N+10],val[N*N+10],sp[N*N+10],stack[N+10];
int tot,top;
double dis[N+10][V+10];
struct S1{
int x,v;
void insert(int _x,int _v){x=_x,v=_v;}
}h[N*V+10],From[N+10][V+10];
bool vis[N+10][V+10];
void join(int x,int y,int v,int l){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=l,sp[tot]=v;}
void SPFA(int x){
int head=0,tail=1;
for (int i=0;i<=N;i++) for (int j=0;j<=V;j++) dis[i][j]=inf;
dis[x][70]=0,h[1].insert(x,70),vis[x][70]=1;
while (head!=tail){
if (++head>N*V) head=1;
int Now=h[head].x,Sp=h[head].v;
for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){
int tmp=!sp[p]?Sp:sp[p];
double Time=1.0*val[p]/tmp;
if (dis[son][tmp]>dis[Now][Sp]+Time){
dis[son][tmp]=dis[Now][Sp]+Time;
From[son][tmp].insert(Now,Sp);
if (!vis[son][tmp]){
if (++tail>N*V) tail=1;
h[tail].insert(son,tmp);
vis[son][tmp]=1;
}
}
}
vis[Now][Sp]=0;
}
}
int main(){
int n=read(),m=read(),T=read()+1;
for (int i=1;i<=m;i++){
int x=read()+1,y=read()+1,v=read(),l=read();
join(x,y,v,l);
}
SPFA(1);
int Sp=0;
for (int i=0;i<=V;i++) if (dis[T][Sp]>dis[T][i]) Sp=i;
int x=T,v=Sp; stack[++top]=T;
while (From[x][v].x){
stack[++top]=From[x][v].x;
S1 tmp=From[x][v];
x=tmp.x,v=tmp.v;
}
for (int i=top;i;i--) printf("%d",stack[i]-1),putchar(i==1?'\n':' ');
}