题目

Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点，欢迎感兴趣的同学参与贡献 https://oi-wiki.org

2834: 回家的路

Time Limit: 10 Sec Memory Limit: 128 MB

Submit: 183 Solved: 98

[][][]

Description

Input

Output

Sample Input

2 1

1 2

1 1 2 2

Sample Output

HINT

N<=20000,M<=100000

Source

[ ][ ][ ]

Back

解法

分层图最短路，将横向与纵向分开即可。

但是只能存下可转移的点与起点和终点。

数据好像有点水，起点和终点好像一定可以换乘

代码

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define INF 2139062143#define MAX 0x7ffffffffffffff#define del(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;template
                
                 inline void read(T&x){ x=0;T k=1;char c=getchar(); while(!isdigit(c)){ if(c=='-')k=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=k;}const int maxn=100000+15;int n,m,s,t,ecnt[2];struct Q{ int x,y,id;}a[maxn];struct Edge { int u,v,w; Edge(int u=0,int v=0,int w=0):u(u),v(v),w(w) {}};vector
                 
                   edge[2];vector
                  
                    G[maxn][2];inline void add_edge(int u,int v,int w,int id) { edge[id].push_back(Edge(u,v,w)); edge[id].push_back(Edge(v,u,w)); ecnt[id]+=2; G[u][id].push_back(ecnt[id]-2); G[v][id].push_back(ecnt[id]-1);}priority_queue< pair
                   
                    
                     ,int> > q;int dis[maxn][2];bool vis[maxn][2];inline void dij() { del(dis,127);dis[s][0]=dis[s][1]=0; q.push(make_pair(make_pair(0,s),0)); q.push(make_pair(make_pair(0,s),1)); while(!q.empty()) { pair
                     
                      
                       ,int> Node=q.top();q.pop(); pair
                       
                         node=Node.first; int id=Node.second,u=node.second,d=-node.first; if(vis[u][id]) continue; vis[u][id]=1; for(int i=0;i
                        
                         d+e.w) { dis[v][id]=d+e.w; q.push(make_pair(make_pair(-dis[v][id],v),id)); } if(dis[v][id^1]>d+e.w+1) { dis[v][id^1]=d+e.w+1; q.push(make_pair(make_pair(-dis[v][id^1],v),id^1)); } } } printf("%d\n",(min(dis[m+2][0],dis[m+2][1])==INF)?-1:min(dis[m+2][0],dis[m+2][1]));}bool cmp1(Q a,Q b) { return (a.x^b.x)?a.x

View Code

转载于:https://www.cnblogs.com/mrasd/p/9853260.html

你可能感兴趣的文章