Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <cstdio>
- #include <vector>
- using namespace std;
- vector<int> tsort;
- int n, m;
- int s,t;
- int v1, v2, v3;
- vector<pair<int, int>> *arr;
- bool* visited;
- void dfs(int i)
- {
- visited[i] = true;
- for(size_t j = 0; j < arr[i].size(); j++)
- if (!visited[arr[i][j].first])
- dfs(arr[i][j].first);
- tsort.push_back(i);
- }
- int main()
- {
- ifstream in("shortpath.in");
- ofstream out("shortpath.out");
- in >> n >> m >> s >> t;
- --s;
- --t;
- visited = new bool [n];
- arr = new vector<pair<int,int>> [n];
- for (int i = 0; i < n; i++)
- {
- visited[i] = false;;
- }
- pair<int, int> p;
- for(int i = 0; i < m; i++)
- {
- in >> v1 >> v2 >> v3;
- v1--;
- v2--;
- p.first = v2;
- p.second = v3;
- arr[v1].push_back(p);
- }
- for(int i = 0; i < n; i++)
- if(!visited[i])
- dfs(i);
- int v;
- int *d;
- d = new int [n];
- for (int i = 0; i < n; i++)
- d[i] = 1001;
- d[s] = 0;
- for(int i = (n - 1); i >= 0 ; i--)
- {
- v = tsort[i];
- if (d[v] == 1001) continue;
- for (size_t j = 0; j < arr[v].size(); j++)
- d[arr[v][j].first] = min(d[arr[v][j].first],d[v] + arr[v][j].second);
- }
- if(d[t] == 1001)
- out << "Unreachable";
- else
- out << d[t];
- }
Add Comment
Please, Sign In to add comment