[双连通分量+队列优化dijkstra]acdream 1415

题意：

       给出一个n个点，m条边无向图(2 ≤ n ≤ 20 000, 1 ≤ m ≤ 100 000).。求出存在哪些边，使得去掉这些边之后，最短路的长度会增加。

 

思路：

       第一步求出最短路，并判断出哪些边可以在最短路上。并用这些边重新建图。

       第二步，用第一步建出的图求出割边，得到的割边就是答案

       要注意tarjan时可能会出现重边

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int nMax=20050;
const int mMax=400005 ;
const long long inf= 1e18 ;

struct{
    int u,v, next;
    int  w;
    int num;
}edge[mMax],edge1[mMax];
int n,k, head[nMax],head1[nMax],k1;
int que[nMax];
bool vis[nMax];

void addedge(int a,int b,int w,int num){
    edge[k].w = w;
    edge[k].u=a;
    edge[k].v=b;
    edge[k].num=num;
    edge[k].next=head[a];
    head[a]=k;k++;
}
void addedge1(int a,int b,int num){
    edge1[k1].u=a;
    edge1[k1].v=b;
    edge1[k1].num=num;
    edge1[k1].next=head1[a];
    head1[a]=k1;k1++;
}


struct node{
    int u;
    long long dis;
    bool operator < (const node &a) const{        //  heap的重载 < 号的形式。
        return dis > a.dis;
    }
};
void dijkstra(int s ,long long dis[nMax]){
    for(int i = 1; i <= n; i ++){
        dis[i] = inf;
        vis[i] = false;
    }
    dis[s] = 0;
    priority_queue<node> que;    //  运用STL的优先队列。
    node a;
    a.u = s; a.dis = 0;
    que.push(a);
    while(!que.empty()){
        int u = que.top().u;
        que.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; i != 0; i = edge[i].next){
            int v = edge[i].v;
            if(!vis[v] && dis[v] > dis[u] + edge[i].w){
                dis[v] = dis[u] + edge[i].w;
                a.u = v; a.dis = dis[v];
                que.push(a);
            }
        }
    }
}
long long dis[nMax];
long long dis1[nMax];

int dep,nbridge;
int dfn[nMax],low[nMax],res[mMax];

void Tarjan(int u,int fa){                        //我的割边模版
    dfn[u]=low[u]=++dep;
    int flag = 1 ;
    for(int i=head1[u];i;i=edge1[i].next){
        int v=edge1[i].v;
        if ( v == fa && flag ) {
            flag = 0 ;
            continue ;
        }
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
               res[++nbridge]=edge1[i].num;
            }
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
}

int main(){
    int i,m,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF){
        k=1;
        memset(head,0,sizeof(head));
        k1=1;
        memset(head1,0,sizeof(head1));


        for(i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c,i);
            addedge(b,a,c,i);
        }

        dijkstra(1,dis);
        dijkstra(n,dis1);
        for(i=1;i<k;i++){
            int u=edge[i].u;
            int v=edge[i].v;
            if(dis[u]+edge[i].w+dis1[v]==dis[n]||dis[v]+edge[i].w+dis1[u]==dis[n]){
                addedge1(u,v,edge[i].num);
            }
        }

        dep=0;
        nbridge=0;
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        for(i=1;i<=n;i++)if(!dfn[i])Tarjan(i,-1);

        printf("%d\n",nbridge);
        if(nbridge){
            for(i=1;i<nbridge;i++){
                printf("%d ",res[i]);
            }printf("%d\n",res[nbridge]);
        }
    }
    return 0;
}