1111. Online Map (30)-白红宇

1111. Online Map (30)

阅读量：6771 次

发布时间：2019-06-26

本文共 3803 字，大约阅读时间需要 12 分钟。

解题思路：

Dijkstra储存最短路径，dfs找最优路径

破题，呸(:з」∠)

AC代码

//简化了一下代码，2017.9.7#include 
     
      #include 
      
       #include 
       
        using namespace std;const int Inf=999999;int vn,an,s,e;vector
        
         
          > vT(512,vector
          
           (512,Inf));//timeAdjMvector
           
            
             > vL(512,vector
             
              (512,Inf));//lengthAdjMvector
              
                sp,fp;//储存最终结果路径，最短和最快int mintime=Inf,ansdis=-1;//最短路径不唯一，取时间最短int minsect=Inf,anstim=-1;//最短时间不唯一，取最少交叉口void dijkstra(vector
               
                
                 > &v,vector
                 
                  
                   > &path)//dijkstra求解满足初始条件的所有解，v为邻接矩阵，path返回保存路径{ vector
                   
                     dis(v[s]); vector
                    
                      vis(vn,false); vis[s]=true; while(true) { int mind=Inf,u=-1; for(int j=0;j
                     
                      dis[u]+v[u][w]) { dis[w]=dis[u]+v[u][w]; path[w].clear(); path[w].push_back(u); } else if(!vis[w]&&dis[w]==dis[u]+v[u][w]) path[w].push_back(u); } }}void shortpath(vector
                      
                       
                        >&lenp,vector
                        
                          &rp,int cur,int timesum,int dis)//dfs筛选最优路径{ if(s==cur&&timesum

>&timp,vector

&rp,int cur,int tim,int seccnt)//dfs筛选最优路径{ if(s==cur&&seccnt

>vn>>an; for(int i=0;i

>u>>w>>oneway>>length>>time; vL[u][w]=length; vT[u][w]=time; if(oneway==0) { vL[w][u]=length; vT[w][u]=time; } } cin>>s>>e; vector

> timp(vn),lenp(vn);//时间路径，长度路径 for(int i=0;i

rp;//记录可能的路径 shortpath(lenp,rp,e,0,0); fastpath(timp,rp,e,0,0); if(sp==fp) { printf("Distance = %d; Time = %d: ",ansdis,anstim); for(auto it=sp.rbegin();it!=sp.rend();++it) printf("%d -> ",*it); printf("%d\n",e); } else { printf("Distance = %d: ",ansdis); for(auto it=sp.rbegin();it!=sp.rend();++it) printf("%d -> ",*it); printf("%d\n",e); printf("Time = %d: ",anstim); for(auto it=fp.rbegin();it!=fp.rend();++it) printf("%d -> ",*it); printf("%d\n",e); } return 0;}

//previous_code#include 
     
      #include 
      
       using namespace std;const int maxv=502,INF=0x7fffffff;int n,m,s,e;int arclen[maxv][maxv],arctim[maxv][maxv];int distim[maxv],dislen[maxv],vistim[maxv],vislen[maxv];vector
       
         sp[maxv],temps,anss;vector
        
          fp[maxv],tempf,ansf;int mintime=0x7fffffff,minsec=0x7fffffff;int distancex=0x7fffffff,time=0;void InitAdjMatrix(){    for(int i=0;i
         
          timecnt))        {            mintime=timecnt;            anss.clear();            anss=temps;            distancex=discnt;        }    }    for(auto it=sp[u].begin();it!=sp[u].end();++it)    {        dfsSP(*it,timecnt+arctim[*it][u],discnt+arclen[*it][u]);    }    temps.pop_back();}void FastPath(){    int min,v;    for(int i=0;i
          
            ",*it):printf("%d\n",*it); return 0; } printf("Distance = %d: ",distancex); for(auto it=anss.rbegin();it!=anss.rend();++it) it!=anss.rend()-1?printf("%d -> ",*it):printf("%d\n",*it); printf("Time = %d: ",time); for(auto it=ansf.rbegin();it!=ansf.rend();++it) it!=ansf.rend()-1?printf("%d -> ",*it):printf("%d\n",*it); return 0;}

直接dfs最后一个测试点是会超时的（毕竟有五百个点）

如下面这个代码：

#include 
     
      #include 
      
       using namespace std;const int maxv=502;int arclen[maxv][maxv],arctim[maxv][maxv];int minsec=0x7fffffff,mintime=0x7fffffff,mintimeOfminlen=0x7fffffff,minlen=0x7fffffff;int s,e,viss[maxv],visf[maxv],vis[maxv];vector
       
         anss,ansf,p;vector
        
          v[maxv];void dfs(int u,int vcnt,int timecnt,int lencnt){    vis[u]=1;    p.push_back(u);    if(u==e)    {        if(lencnt
         
          
            ",*it):printf("%d\n",*it); return 0; } printf("Distance = %d: ",minlen); for(auto it=anss.begin();it!=anss.end();++it) it!=anss.end()-1?printf("%d -> ",*it):printf("%d\n",*it); printf("Time = %d: ",mintime); for(auto it=ansf.begin();it!=ansf.end();++it) it!=ansf.end()-1?printf("%d -> ",*it):printf("%d\n",*it); return 0;}

转载于:https://www.cnblogs.com/xLester/p/7570322.html