poj 1797 - Heavy Transportation (최대 변, 최 단 로 변형 spfa)

제목 의 대의:
T 를 드 리 겠 습 니 다. T 팀 의 테스트 데 이 터 를 대표 합 니 다. n 은 n 개의 점 이 있 고 m 는 m 개의 변 이 있 습 니 다. 각 변 에 세 개의 매개 변수 가 있 습 니 다. a, b, c 는 a 에서 b 까지 의 이 길에서 가장 큰 감당 무 게 는 c 입 니 다.
당신 에 게 이 노선 에서 가장 작은 하중 을 요구 하고 모든 다른 노선 에서 가장 큰 선 로 를 찾 게 합 니 다.
제목 분석:
여기 서 spfa 를 변형 시 키 기만 하면 이 문 제 를 해결 할 수 있다.
우선 우리 dist 배열 은 시작 위 치 를 INF 로 초기 화하 고 다른 위 치 는 0 으로 초기 화 합 니 다.
그리고 dist 배열 을 업데이트 합 니 다. 결 과 는 dist [n] 를 출력 하면 됩 니 다.
왜 이렇게 썼 습 니까? 왜냐하면 우 리 는 매번 모든 경로 의 가장 큰 변 의 가장 작은 하 나 를 찾 아야 하기 때 문 입 니 다.
전달 식 은 dist [e] = max (dist [e], min (dist [s], G [s] [i]) 이다.
다음은 코드:
 

 1 #include <iostream>

 2 #include <cstdlib>

 3 #include <cstdio>

 4 #include <algorithm>

 5 #include <vector>

 6 #include <queue>

 7 using namespace std;

 8 #define INF 0xfffffff

 9 #define maxn 1050

10 

11 struct Edge

12 {

13     int e;

14     long long w;

15 };

16 vector<Edge> G[maxn];

17 long long dist[maxn];

18 bool vis[maxn];

19 int m, n;

20 long long Spfa()

21 {

22     Edge P, Pn;

23     P.e = 1, P.w = 0;

24     queue <Edge> Q;

25     Q.push(P);

26 

27     while( !Q.empty() )

28     {

29         P = Q.front();

30         Q.pop();

31         vis[P.e] = false;

32         int len = G[P.e].size();

33 

34         for(int i=0; i<len; i++)

35         {

36             Pn = G[P.e][i];

37 

38             if(dist[Pn.e] < min(dist[P.e],Pn.w) )

39             {

40                 dist[Pn.e] = min(dist[P.e],Pn.w);

41 

42                 if(!vis[Pn.e])

43                 {

44                     vis[Pn.e] = true;

45                     Q.push(Pn);

46                 }

47             }

48         }

49     }

50     return dist[n];

51 }

52 void Init()

53 {

54     for(int i=1; i<=n ;i++)

55     {

56         G[i].clear();

57         vis[i] = false;

58         dist[i] = 0;

59     }

60     dist[1] = INF;

61 }

62 int main()

63 {

64     int T, cas = 1;

65     Edge P;

66     cin >> T;

67 

68     while(T--)

69     {

70         scanf("%d%d",&n,&m);

71 

72         Init();

73         for(int i=0; i<m; i++)

74         {

75             int a, b, c;

76             scanf("%d%d%d",&a,&b,&c);

77             P.e = b, P.w = c;

78 

79             G[a].push_back(P);

80 

81             P.e = a;

82 

83             G[b].push_back(P);

84         }

85         long long ans = Spfa();

86 

87         printf("Scenario #%d:
%lld
",cas++,ans);

88         if(T)

89             printf("
");

90 

91     }

92     return 0;

93 }