程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ASC(22)C(最短路+雙連通分量找橋或拓撲排序)

ASC(22)C(最短路+雙連通分量找橋或拓撲排序)

編輯:C++入門知識

ASC(22)C(最短路+雙連通分量找橋或拓撲排序)


Important Roads

Special JudgeTime Limit: 20000/10000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others) SubmitStatisticNext Problem

Problem Description

The city where Georgie lives has n junctions some of which are connected by bidirectional roads.
Every day Georgie drives from his home to work and back. But the roads in the city where Georgie lives are very bad, so they are very often closed for repair. Georgie noticed that when some roads are closed he still can get from home to work in the same time as if all roads were available.

But there are such roads that if they are closed for repair the time Georgie needs to get from home to work increases, and sometimes Georgie even cannot get to work by a car any more. Georgie calls such roads important.
Help Georgie to find all important roads in the city.

Input

The first line of the input file contains n and m — the number of junctions and roads in the city where Georgie lives, respectively (2 ≤ n ≤ 20 000, 1 ≤ m ≤ 100 000). Georgie lives at the junction 1 and works at the junction n.

The following m lines contain information about roads. Each road is specified by the junctions it connects and the time Georgie needs to drive along it. The time to drive along the road is positive and doesn’t exceed 100 000. There can be several roads between a pair of junctions, but no road connects a junction to itself. It is guaranteed that if all roads are available, Georgie can get from home to work.

Output

Output l — the number of important roads — at the first line of the output file. The second line must contain l numbers, the numbers of important roads. Roads are numbered from 1 to m as they are given in the input file.

Sample Input

6 7
1 2 1
2 3 1
2 5 3
1 3 2
3 5 1
2 4 1
5 6 2

Sample Output

2
5 7

題意:給出一個無向圖,起點為1,終點為n,要求的是找出一些邊,這些邊滿足,刪掉以後從起點到終點的最短路的長度會變小
思路:先求出起點到各個點的最短路,用dj+堆優化,spfa不穩定很惡心
然後可以根據各個點的最短路的值處理出最短路的圖,這個圖裡所有的邊都是最短路上的邊且滿足任何點都能走到終點
處理出了這個圖以後有兩種做法
1.可以將最短路圖處理成無向圖,然後用雙連通分量找橋即可,橋就是題目要找的邊,因為刪掉以後一定不能再從起點走到終點
2.將最短路圖處理成單向的,就是只有起點往終點的方向,不難發現這是一個拓撲圖,然後按拓撲排序的順序遍歷這張圖
設置一個全局變量,記錄的是所有點的出度與入度的差值,如果當前這個差值為1,那麼當前的點所指向的邊一定是題目要找的邊
這個方法是隊友想出來的 Orz...
下面是兩種方法的代碼
方法1:
方法2:

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved