道路和航线

未分类

在此输入正文

#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;
}