Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <functional>
- #include <set>
- #include <tuple>
- #define MAXN (200000+10)
- #define MAXM (500000+10)
- #define INF (100000000000000000ll)
- typedef long long int lli;
- typedef std::pair<lli,lli> pii;
- int n, m, s, t;
- std::vector<int> nei[MAXN];
- std::vector<int> wei[MAXN];
- std::vector<int> dan[MAXN];
- lli sd[MAXN]; // shortest distance
- bool visited[MAXN];
- inline void init_visited(){
- for(int i = 0; i < n; ++i) visited[i] = false;
- }
- bool reachable(int from, const int &allowed_danger){
- // DFS
- if(from == t) return true;
- if(visited[from]) return false;
- visited[from] = true;
- for(size_t i = 0; i < nei[from].size(); ++i){
- if(dan[from][i] > allowed_danger) continue;
- if(nei[from][i] == t) return true;
- if(reachable(nei[from][i], allowed_danger)) return true;
- }
- return false;
- }
- int main(){
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(0);
- std::cin >> n >> m >> s >> t;
- for(int i = 0; i < m; ++i){
- int x, y, d, l;
- std::cin >> x >> y >> d >> l;
- nei[x].push_back(y);
- wei[x].push_back(d);
- dan[x].push_back(l);
- nei[y].push_back(x);
- wei[y].push_back(d);
- dan[y].push_back(l);
- }
- // binary search for the minimal L
- // L in (l,r]
- int L;
- {
- int l = -1, r = 1000000000;
- while(l+1 != r){
- int mid = (l+r+1) / 2;
- init_visited();
- if(reachable(s, mid)) r = mid;
- else l = mid;
- }
- L = r;
- }
- // calculate shortest path using Dijkstra's
- std::set<pii> upcoming; // first: distance; second: vertex index
- for(int i = 0; i < n; ++i){
- sd[i] = (i == s) ? 0 : INF;
- upcoming.insert(pii(sd[i], i));
- }
- while(!upcoming.empty()){
- int v = upcoming.begin()->second;
- if(v == t) break;
- upcoming.erase(upcoming.begin());
- for(size_t i = 0; i < nei[v].size(); ++i){
- if(dan[v][i] > L) continue;
- int v2 = nei[v][i];
- // relax
- if(sd[v2] > sd[v] + wei[v][i]){
- upcoming.erase(upcoming.find(pii(sd[v2], v2)));
- sd[v2] = sd[v] + wei[v][i];
- upcoming.insert(pii(sd[v2], v2));
- }
- }
- }
- std::cout << sd[t] << ' ' << L << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement