[关闭]
@fuheimao 2015-09-30T07:46:23.000000Z 字数 1930 阅读 33

道路和航线

未分类


在此输入正文

  1. #include "cstring"
  2. #include "iostream"
  3. #include "vector"
  4. #include "stack"
  5. #include "queue"
  6. using namespace std;
  7. struct Edge{
  8. int From, To, Value;
  9. bool operator < (const Edge& b) const {
  10. return Value < b.Value;
  11. }
  12. };
  13. typedef pair<int, int> Node;
  14. vector<Edge> Graph[25001];
  15. vector<Edge> GraphOpp[25001];
  16. vector<Edge> G[25001];
  17. stack<int> Numbers;
  18. int T, R, P, S;
  19. int Visited[25001];
  20. int Distant[25001];
  21. /*void Dijkstra(){
  22. memset(Visited, 0, sizeof(Visited));
  23. priority_queue<Edge> Q;
  24. for (int i = 1; i <= n; ++i){
  25. while (Q.size() && Visited[Q.top().Label]) Q.pop();
  26. if (Q.empty()) break;
  27. Edge Now = Q.top();
  28. Q.pop();
  29. Visited[Now.Label] = true;
  30. for (vector<Edge>::iterator j = Graph[Now.Label].begin(); j != Graph[Now.Label].end(); ++j){
  31. if (!Visited[j -> To] && Distant[j -> To][X] > Distant[Now.Label][X] + j -> Value){
  32. Distant[j -> To][X] = Distant[Now.Label][X] + j -> Value;
  33. Q.push((Edge){j -> To, Distant[j -> To][X]});
  34. }
  35. }
  36. }
  37. }*/
  38. int Number = 1;
  39. void DFS1(int x, stack<Edge>& Edges){
  40. Visited[x] = true;
  41. for (vector<Edge>::iterator i = Graph[x].begin(); i != Graph[x].end(); ++i){
  42. if (!Visited[i->To]){
  43. DFS1(i->To, Edges);
  44. Edges.push(*i);
  45. }
  46. }
  47. }
  48. void DFS2(int x, int Number){
  49. Visited[x] = true;
  50. for (vector<Edge>::iterator i = GraphOpp[x].begin(); i != GraphOpp[x].end(); ++i){
  51. if (!Visited[i->To]){
  52. DFS2(i->To, Number);
  53. G[Number].push_back(*i);
  54. }
  55. }
  56. }
  57. void Kosaraju(){
  58. memset(Visited, 0, sizeof(Visited));
  59. stack<Edge> Edges;
  60. DFS1(S, Edges);
  61. memset(Visited, 0, sizeof(Visited));
  62. int B = 0;
  63. while (!Edges.empty()){
  64. Edge Now = Edges.top();
  65. Edges.pop();
  66. int To = Now.To;
  67. if (!B){
  68. B = 1;
  69. To = Now.From;
  70. }
  71. if (!Visited[To]){
  72. DFS2(To, Number++);
  73. }
  74. }
  75. }
  76. int main(){
  77. ios::sync_with_stdio(false);
  78. cin >> T >> R >> P >> S;
  79. for (int i = 1; i <= R; ++i){
  80. int f, t, v;
  81. cin >> f >> t >> v;
  82. Graph[f].push_back((Edge){f, t, v});
  83. Graph[t].push_back((Edge){t, f, v});
  84. GraphOpp[f].push_back((Edge){f, t, v});
  85. GraphOpp[t].push_back((Edge){t, f, v});
  86. }
  87. for (int i = 1; i <= P; ++i){
  88. int f, t, v;
  89. cin >> f >> t >> v;
  90. Graph[f].push_back((Edge){f, t, v});
  91. Graph[t].push_back((Edge){t, f, v});
  92. }
  93. Kosaraju();
  94. for (int j = 1; j < Number; ++j){
  95. for (vector<Edge>::iterator i = G[j].begin(); i != G[j].end(); ++i){
  96. cout << i->From << "->" << i->To;
  97. }
  98. cout << endl;
  99. }
  100. return 0;
  101. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注