@fuheimao
2015-09-30T15:46:23.000000Z
字数 1930
阅读 623
未分类
在此输入正文
#include "cstring"
#include "iostream"
#include "vector"
#include "stack"
#include "queue"
using namespace std;
struct Edge{
int From, To, Value;
bool operator < (const Edge& b) const {
return Value < b.Value;
}
};
typedef pair<int, int> Node;
vector<Edge> Graph[25001];
vector<Edge> GraphOpp[25001];
vector<Edge> G[25001];
stack<int> Numbers;
int T, R, P, S;
int Visited[25001];
int Distant[25001];
/*void Dijkstra(){
memset(Visited, 0, sizeof(Visited));
priority_queue<Edge> Q;
for (int i = 1; i <= n; ++i){
while (Q.size() && Visited[Q.top().Label]) Q.pop();
if (Q.empty()) break;
Edge Now = Q.top();
Q.pop();
Visited[Now.Label] = true;
for (vector<Edge>::iterator j = Graph[Now.Label].begin(); j != Graph[Now.Label].end(); ++j){
if (!Visited[j -> To] && Distant[j -> To][X] > Distant[Now.Label][X] + j -> Value){
Distant[j -> To][X] = Distant[Now.Label][X] + j -> Value;
Q.push((Edge){j -> To, Distant[j -> To][X]});
}
}
}
}*/
int Number = 1;
void DFS1(int x, stack<Edge>& Edges){
Visited[x] = true;
for (vector<Edge>::iterator i = Graph[x].begin(); i != Graph[x].end(); ++i){
if (!Visited[i->To]){
DFS1(i->To, Edges);
Edges.push(*i);
}
}
}
void DFS2(int x, int Number){
Visited[x] = true;
for (vector<Edge>::iterator i = GraphOpp[x].begin(); i != GraphOpp[x].end(); ++i){
if (!Visited[i->To]){
DFS2(i->To, Number);
G[Number].push_back(*i);
}
}
}
void Kosaraju(){
memset(Visited, 0, sizeof(Visited));
stack<Edge> Edges;
DFS1(S, Edges);
memset(Visited, 0, sizeof(Visited));
int B = 0;
while (!Edges.empty()){
Edge Now = Edges.top();
Edges.pop();
int To = Now.To;
if (!B){
B = 1;
To = Now.From;
}
if (!Visited[To]){
DFS2(To, Number++);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin >> T >> R >> P >> S;
for (int i = 1; i <= R; ++i){
int f, t, v;
cin >> f >> t >> v;
Graph[f].push_back((Edge){f, t, v});
Graph[t].push_back((Edge){t, f, v});
GraphOpp[f].push_back((Edge){f, t, v});
GraphOpp[t].push_back((Edge){t, f, v});
}
for (int i = 1; i <= P; ++i){
int f, t, v;
cin >> f >> t >> v;
Graph[f].push_back((Edge){f, t, v});
Graph[t].push_back((Edge){t, f, v});
}
Kosaraju();
for (int j = 1; j < Number; ++j){
for (vector<Edge>::iterator i = G[j].begin(); i != G[j].end(); ++i){
cout << i->From << "->" << i->To;
}
cout << endl;
}
return 0;
}