有n个岛屿， m座桥，每座桥连通两座岛屿，桥上会有一些敌人，玩家只有消灭了桥上的敌人才能通过，与此同时桥上的敌人会对玩家造成一定伤害。而且会有一个大Boss镇守一座桥，以玩家目前的能力，是不可能通过的。而Boss是邪恶的， Boss会镇守某一座使得玩家受到最多的伤害才能从岛屿1到达岛屿n(当然玩家会选择伤害最小的路径)。问， Boss可能镇守岛屿有哪些。

Solution

我们可以先找出一条最短路，那么我们要删去一条边的话，肯定要从这条路中删。

那么接着考虑一条不在这条路径上的边能够产生的贡献。

看起来有点麻烦，我们可以对于每个不在最短路上的点求一个pre一个nex，大概是这个意思(不太好用文字表述)。

这里的pre是最靠右的，next是最靠左的、

那么这条边能够产生贡献的条件是pre到next中的某条边被删掉。此时的最短路可能为dis[1][x]+l+dis[x][n].。

所以我们要对所有情况取min，这时可以用线段树维护最短路链，区间取min。

Code

 

#include
     
      #include
      
       #include
       
        #include
        
         #define N 100002#define mm make_pair#define inf 0x3f3f3f3fusing namespace std;queue
         
          q;int head[N],tot,n,m,dis[2][N],pre[N],tr[N<<2],la[N<<2],ans1,ans2,tag[N],s_t[N],l[N],top,r[N]; bool vis[N],gan[N<<2];struct node{    int n,to,l;}e[N<<2];inline void add(int u,int v,int l){    e[++tot].n=head[u];    e[tot].to=v;    e[tot].l=l;    head[u]=tot;}inline void dij(int s,int tag){    memset(dis[tag],0x3f,sizeof(dis[tag]));    memset(vis,0,sizeof(vis));    priority_queue
          
           
             >q; q.push(mm(0,s));dis[tag][s]=0; while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u])continue;vis[u]=1; for(int i=head[u];i;i=e[i].n){ int v=e[i].to; if(dis[tag][v]>dis[tag][u]+e[i].l){ dis[tag][v]=dis[tag][u]+e[i].l;pre[v]=u; q.push(mm(-dis[tag][v],v)); } } } }void BFS(int s,int *a,int ta){ q.push(s);a[s]=s; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].n)if(!a[e[i].to]&&!tag[e[i].to]){ if(dis[ta][e[i].to]!=dis[ta][u]+e[i].l)continue; int v=e[i].to;a[v]=s;q.push(v); } }}inline void pushdown(int cnt){ if(la[cnt]
            
             <<1]){tr[cnt<<1]=la[cnt];la[cnt<<1]=la[cnt];} if(la[cnt]
             
              <<1|1]){tr[cnt<<1|1]=la[cnt];la[cnt<<1|1]=la[cnt];} la[cnt]=inf;} void upd(int cnt,int l,int r,int L,int R,int x){ if(l>=L&&r<=R){ if(x
              
               >1; if(la[cnt]!=inf)pushdown(cnt); if(mid>=L)upd(cnt<<1,l,mid,L,R,x); if(mid
               
                <<1|1,mid+1,r,L,R,x); tr[cnt]=max(tr[cnt<<1],tr[cnt<<1|1]);}void dfs(int cnt,int l,int r){ if(l==r){ if(l!=1){ if(tr[cnt]>ans1){ans1=tr[cnt];ans2=1;} else if(tr[cnt]==ans1)ans2++; } return; } int mid=(l+r)>>1; if(la[cnt]!=inf)pushdown(cnt); dfs(cnt<<1,l,mid);dfs(cnt<<1|1,mid+1,r);}int main(){ scanf("%d%d",&n,&m);int u,v,w;tot=1; for(int i=1;i<=m;++i){ scanf("%d%d%d",&u,&v,&w); add(u,v,w);add(v,u,w); } dij(1,0);int s=n;while(s!=1)s_t[++top]=s,tag[s]=top,s=pre[s];s_t[++top]=1;tag[1]=top; dij(n,1); for(int i=1;i<=n;++i) for(int j=head[i];j;j=e[j].n){ int v=e[j].to; if(dis[0][i]+dis[1][v]+e[j].l==dis[0][n]&&tag[i]&&tag[v])gan[j]=gan[j^1]=1; } for(int i=1;i<=top;++i)BFS(s_t[i],l,0); //t->s for(int i=top;i>=1;--i)BFS(s_t[i],r,1); //s->t memset(tr,0x3f,sizeof(tr));memset(la,0x3f,sizeof(la)); for(int i=1;i<=n;++i) for(int j=head[i];j;j=e[j].n)if(!gan[j]&&tag[l[i]]>tag[r[e[j].to]]){ int v=e[j].to; // cout<
                
                 <<" "<
                 
                  <<" "<
                  
                   <