Codeforces E. President and Roads (优先队列Dijkstar + 强连通 找必最短路上的必须边（桥）)经典(二)
间 和 从 vt 反向到每个点的最短时间 bool inq[N]; void init() { eid=0; memset(head,-1,sizeof(head)); } void addEdg(int u ,int v,ll t,ll tt=0) { edg[eid].to=v; edg[eid].next=head[u]; edg[eid].t=t; head[u]=eid++; edg[eid].to=u; edg[eid].next=head[v]; edg[eid].t=tt; head[v]=eid++; } void dijstar(int flag) { priority_queue
q; NNNN now , pre; int u,v; for(int i=1; i<=n; i++){ if(flag==0) time1[i]=INF; else time2[i]=INF; inq[i]=0; } now.t = 0; if(flag==0) time1[vs]=0 , now.u = vs; else time2[vt]=0 , now.u = vt; q.push(now); while(!q.empty()) { pre=q.top(); q.pop(); u=pre.u; if(inq[u]) continue; inq[u]=1; for(int i=head[u]; i!=-1; i=edg[i].next){ v=edg[i].to; if(inq[v])continue; if(flag==0){ if(time1[v]>time1[u]+edg[i].t&&edg[i].t!=INF){ time1[v]=time1[u]+edg[i].t; now.t = time1[v] ; now.u = v; q.push(now); } } else{ //反向求最短时间 int ti=i^1; if(time2[v]>time2[u]+edg[ti].t&&edg[i].t==INF){ time2[v]=time2[u]+edg[ti].t; now.t = time2[v] ; now.u = v; q.push(now); } } } } } bool ok[N] , vistedg[N]; int low[N] , dfn[N] , deep ; void tarjar(int u ) { low[u] = dfn[u] = ++deep; for(int i=head[u] ; i!=-1; i=edg[i].next){ int v=edg[i].to ; if(vistedg[edg[i].t]){ //有重边找必经路，只能用标记边的办法才会正确，不用 v==f head[u] = edg[i].next; continue; } head[u] = edg[i].next; //每条边只用一次 vistedg[edg[i].t] = 1; if( !dfn[v] ){ tarjar( v ) ; low[u] = low[u] < low[v] ? low[u] : low[v] ; if(dfn[u] < low[v]) ok[edg[i].t]=1; //桥，则是必经路 } else if(low[u]>dfn[v]) low[u] = dfn[v] ; } } int main() { int m , u , v ; ll t; while(scanf(%d%d%d%d,&n,&m,&vs,&vt)>0){ init(); for(int i=0; i
0) printf(CAN %I64d ,node[i].t-t); else printf(NO ); } } }
?
?
|