Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment (linker, "/STACK:64000000")
- #include <fstream>
- #include <vector>
- #include <stack>
- #include <cstdio>
- using namespace std;
- struct edje_to
- {
- int to;
- int weght;
- };
- vector<edje_to>* edjes;
- vector<int> nodes;
- int* colors;
- int* weights;
- int m, n;
- int a, b;
- int s, t;
- edje_to p;
- bool path = false;
- void topsort(int v)
- {
- colors[v] = 1;
- for (int i = 0; i < edjes[v].size(); i++)
- {
- if (colors[edjes[v][i].to] == 0)
- {
- topsort(edjes[v][i].to);
- }
- }
- colors[v] = 2;
- nodes.push_back(v);
- }
- int main()
- {
- ifstream in;
- ofstream out;
- in.open("shortpath.in");
- in >> n >> m >> s >> t;
- edjes = new vector<edje_to> [n];
- colors = new int [n];
- weights = new int [n];
- for (int i = 0; i < n; i++)
- {
- colors[i] = 0;
- weights[i] = 2100000000;
- }
- for (int i = 0; i < m; i++)
- {
- in >> a >> p.to >> p.weght;
- p.to--;
- edjes[a - 1].push_back(p);
- }
- in.close();
- for(int i = 0; i < n; i++)
- {
- if(colors[i] == 0)
- {
- topsort(i);
- }
- }
- a = 0;
- for(int i = nodes.size() - 1; i > 0; i--)
- {
- if(nodes[i] == s - 1)
- {
- a = i;
- break;
- }
- }
- weights[s - 1] = 0;
- for(int i = a; i >= 0; i--)
- {
- for(int j = 0; j < edjes[nodes[i]].size(); j++)
- {
- if(weights[edjes[nodes[i]][j].to] > weights[nodes[i]] + edjes[nodes[i]][j].weght)
- {
- weights[edjes[nodes[i]][j].to] = weights[nodes[i]] + edjes[nodes[i]][j].weght;
- }
- }
- }
- out.open("shortpath.out");
- if(weights[t - 1] == 2100000000)
- {
- out << "Unreachable";
- }
- else
- {
- out << weights[t - 1];
- }
- out.close();
- return 0;
- }
Add Comment
Please, Sign In to add comment