题目描述

给定一个无向图 G,对于其中的一条边(u,v),将它删除之后会使得从 1 到 n

的最短路长度增加,那么这条边被称为“重要道路”。

求 G 中所有的重要道路。

输入格式

第一行两个整数 n,m,分别代表点数和边数。

接下来 m 行,每行三个整数 u,v,c,代表权值为 c 的无向边(u,v)。可能有重

边,但没有自环。保证 1 号点和 n 号点是连通的。

输出格式

第一行一个整数 k,代表重要道路的数量。

下一行升序输出 k 个数代表重要道路的编号(按输入顺序从 1 到 m)。

输入样例

6 7

1 2 1

2 3 1

2 5 3

1 3 2

3 5 1

2 4 1

5 6 2

输出样例

2

5 7

数据规模

20%的数据,n,m<=10。

另外 20%的数据,m=n-1。

100%的数据,1<=n<=20000,1<=m,c<=100000。

SPFA求最短路

求出所有在最短路上的边

求出这些边的割边(桥)

此题卡SPFA，要用单调队列优化

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 struct Node 9 { 10 int next,to,dis,id; 11 }edge[400001]; 12 struct Edge 13 { 14 int u,v,w; 15 }e[200001]; 16 struct ZYYS 17 { 18 int x,d; 19 bool operator < (const ZYYS &a) 20 const 21 { 22 return d>a.d; 23 } 24 }; 25 int dist[200001],vis[200001],head[200001],num,ban[200001],n,m,d,ans,a[200001],dist2[200001]; 26 int dfn[200001],low[200001],cnt,instack[200001]; 27 void add(int u,int v,int dis,int id) 28 { 29 num++; 30 edge[num].next=head[u]; 31 head[u]=num; 32 edge[num].to=v; 33 edge[num].dis=dis; 34 edge[num].id=id; 35 } 36 void SPFA() 37 { int i; 38 priority_queue
           
            Q; 39 for (i=1;i<=n;i++) 40 vis[i]=0,dist[i]=1e9; 41 dist[1]=0; 42 Q.push((ZYYS){ 1,0}); 43 while (Q.empty()==0) 44 { 45 ZYYS u=Q.top(); 46 Q.pop(); 47 vis[u.x]=0; 48 for (i=head[u.x];i;i=edge[i].next) 49 if (ban[i]==0) 50 { 51 int v=edge[i].to; 52 if (dist[v]>dist[u.x]+edge[i].dis) 53 { 54 dist[v]=dist[u.x]+edge[i].dis; 55 if (vis[v]==0) 56 { 57 vis[v]=1; 58 Q.push((ZYYS){v,dist[v]}); 59 } 60 } 61 } 62 } 63 } 64 void SPFA2() 65 { int i; 66 priority_queue
            
             Q; 67 for (i=1;i<=n;i++) 68 dist2[i]=1e9,vis[i]=0; 69 dist2[n]=0; 70 Q.push((ZYYS){n,0}); 71 while (Q.empty()==0) 72 { 73 ZYYS u=Q.top(); 74 Q.pop(); 75 vis[u.x]=0; 76 for (i=head[u.x];i;i=edge[i].next) 77 if (ban[i]==0) 78 { 79 int v=edge[i].to; 80 if (dist2[v]>dist2[u.x]+edge[i].dis) 81 { 82 dist2[v]=dist2[u.x]+edge[i].dis; 83 if (vis[v]==0) 84 { 85 vis[v]=1; 86 Q.push((ZYYS){v,dist[v]}); 87 } 88 } 89 } 90 } 91 } 92 void dfs(int x,int pa) 93 { int flag=0,i; 94 dfn[x]=low[x]=++cnt; 95 instack[x]=1; 96 flag=0; 97 for (i=head[x];i;i=edge[i].next) 98 { 99 int v=edge[i].to;100 if (flag==0&&v==pa)101 {102 flag=1;continue;103 }104 if (dfn[v]==0)105 {106 dfs(v,x);107 low[x]=min(low[v],low[x]);108 if (low[v]>dfn[x]) vis[edge[i].id]=1,ans++;109 }110 else if (instack[v]) low[x]=min(low[x],dfn[v]);111 }112 instack[x]=0;113 }114 int main()115 { int i,u,v,w,j;116 freopen("important.in","r",stdin);117 freopen("important.out","w",stdout);118 cin>>n>>m;119 for (i=1;i<=m;i++)120 {121 scanf("%d%d%d",&u,&v,&w);122 e[i].u=u,e[i].v=v,e[i].w=w;123 add(u,v,w,i);124 add(v,u,w,i);125 }126 SPFA();127 SPFA2();128 memset(vis,0,sizeof(vis));129 for (i=1;i<=n;i++)130 {131 for (j=head[i];j;j=edge[j].next)132 {133 int v=edge[j].to;134 if (dist[i]+edge[j].dis+dist2[v]==dist[n])135 {136 vis[(j+1)/2]=1;137 }138 }139 }140 memset(head,0,sizeof(head));141 num=0;142 for (i=1;i<=m;i++)143 if (vis[i]) add(e[i].u,e[i].v,e[i].w,i),add(e[i].v,e[i].u,e[i].w,i);144 memset(vis,0,sizeof(vis));145 dfs(1,0);146 cout<
             
              <