将每一个点拆成 500 个点, 表示分别表示以某个速度到这里时的最短路, 然后跑最短路即可, 注意距离是 double 类型
- #include<bits/stdc++.h>
- using namespace std;
- #define N 205
- struct ji{
- int nex,to,len,v;
- }edge[N*N];
- struct ji2{
- int k,v;
- }from[N][505];
- queue<ji2>q;
- int E,n,m,k,x,y,v,z,head[N],ans[N],vis[N][505];
- double d[N][505];
- void add(int x,int y,int z,int v){
- edge[E].nex=head[x];
- edge[E].to=y;
- edge[E].len=z;
- edge[E].v=v;
- head[x]=E++;
- }
- void spfa(){
- for(int i=1;i<=n;i++)
- for(int j=1;j<=500;j++)d[i][j]=0x3f3f3f3f;
- d[0][70]=0;
- q.push(ji2{0,70});
- while (!q.empty()){
- ji2 k=q.front();
- q.pop();
- vis[k.k][k.v]=0;
- for(int i=head[k.k];i!=-1;i=edge[i].nex){
- int v=edge[i].to,flag=0;
- if (!edge[i].v){
- flag=1;
- edge[i].v=k.v;
- }
- double x=1.0*edge[i].len/edge[i].v;
- if (d[k.k][k.v]+x<d[v][edge[i].v]){
- from[v][edge[i].v]=k;
- d[v][edge[i].v]=d[k.k][k.v]+x;
- if (!vis[v][edge[i].v]){
- vis[v][edge[i].v]=1;
- q.push(ji2{v,edge[i].v});
- }
- }
- if (flag){
- k.v=edge[i].v;
- edge[i].v=0;
- }
- }
- }
- }
- int main(){
- scanf("%d%d%d",&n,&m,&k);
- memset(head,-1,sizeof(head));
- for(int i=1;i<=m;i++){
- scanf("%d%d%d%d",&x,&y,&v,&z);
- add(x,y,z,v);
- }
- spfa();
- double s=d[k][1];
- for(int i=2;i<=500;i++)s=min(s,d[k][i]);
- for(int i=1;i<=500;i++)
- if (d[k][i]==s){
- ans[++ans[0]]=k;
- ji2 t=from[k][i];
- while (t.k){
- ans[++ans[0]]=t.k;
- t=from[t.k][t.v];
- }
- }
- printf("0");
- for(int i=ans[0];i;i--)printf("%d",ans[i]);
- }
- View Code
[bzoj3245] 最快路线
来源: http://www.bubuko.com/infodetail-3282526.html