算法竞赛进阶指南图论最短路-白红宇

算法竞赛进阶指南图论最短路

阅读量：4493 次

发布时间：2019-06-08

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

题意：一张图，由单向边和双向边组成，每个节点有固定的权值，求从1走到n的最大权值之差

（不知道为啥放最短路里，明明一个bfs就可以解决了

存边时除了单向双向边要注意，还要存一张反边图

bfs一遍记录从1到n每个节点到1的最小权值

再bfs一遍跑反边图，记录从n到1每个节点到n的最大权值

最后遍历一遍统计最大差值就ok了

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;typedef pair
                  
                    P;typedef long double ld;#define mem(x) memset(x, 0, sizeof(x))#define me(x) memset(x, -1, sizeof(x))#define fi first#define se second#define fo(i,n) for(i=0; i
                   
                     q; q.push(1); vis[1]=1; mi[1]=min(mi[1], a[1]); while(q.size()) { ll u=q.front(); q.pop(); for(ll i=head[u]; ~i; i=e[i].nxt) { ll v=e[i].to; mi[v]=min(min(mi[v],a[v]), mi[u]); if(!vis[v]) { vis[v]=1; q.push(v); } } } q.push(n); vi[n]=1; mx[n]=max(mx[n], a[n]); while(q.size()) { ll u=q.front(); q.pop(); for(ll i=head1[u]; ~i; i=e1[i].nxt) { ll v=e1[i].to; mx[v]=max(max(mx[v],a[v]), mx[u]); if(!vi[v]) { vi[v]=1; q.push(v); } } }}int main(){ ll i, j, k; ll n, m; ll u, v; cin>>n>>m; for(i=1; i<=n; i++) cin>>a[i], mi[i]=oo, head[i]=-1, mx[i]=-oo, head1[i]=-1; while(m--) { cin>>u>>v>>k; if(k==1) add(u,v), add1(v,u); else add(u,v), add(v,u), add1(u,v), add1(v,u); } bfs(n); ll ans=0; for(i=1; i<=n; i++) //cout<
                    
                     <<" "<
                     
                      <
                      
                       mi[i]) ans=max(mx[i]-mi[i], ans); } cout<
                       
                        <