UVA 1599 Ideal Path（bfs1+bfs2，双向bfs）-白红宇

UVA 1599 Ideal Path（bfs1+bfs2，双向bfs）

阅读量：5797 次

发布时间：2019-06-18

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

给一个n个点m条边(2<=n<=100000,1<=m<=200000）的无向图，每条边上都涂有一种颜色。求从结点1到结点n的一条路径，使得经过的边数尽量少，在此前提下，经过边的颜色序列的字典序最小。一对结点间可能有多条边，一条边可能连接两个相同结点。输入保证结点1可以达到结点n。颜色为1~10^9的整数。

第一次bfs逆向搜索，得到每个点到终点的最短距离，找出最短路；第二次bfs根据最短距离可以选择满足条件的最短路。

1 #pragma comment(linker, "/STACK:1024000000,1024000000")  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 #include
             
               10 #include
              
                11 #include
                12 #include
                
                  13 #include
                 
                   14 #include 
                  
                    15 using namespace std; 16 int dirx[]={ 0,0,-1,1}; 17 int diry[]={-1,1,0,0}; 18 #define PI acos(-1.0) 19 #define max(a,b) (a) > (b) ? (a) : (b) 20 #define min(a,b) (a) < (b) ? (a) : (b) 21 #define ll long long 22 #define eps 1e-10 23 #define MOD 1000000007 24 #define N 100006 25 #define inf 1e12 26 int n,m; 27 vector
                   
                    G[N]; 28 vector
                    
                     C[N]; 29 int dis[N]; 30 int vis[N]; 31 int ans[N]; 32 void bfs1(){ //得到每一点到终点的最短距离的模板 33 queue
                     
                       q; 34 q.push(n); 35 dis[n]=0; 36 while(!q.empty()){ 37 int u=q.front(); 38 q.pop(); 39 40 for(int i=0;i