@fuheimao 2015-09-30T07:46:23.000000Z 字数 1930 阅读 552

道路和航线

未分类

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

• 私有
• 公开
• 删除