Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*input
- 5 5
- 0 4
- 0 1 1 3
- 0 2 2 2
- 1 3 1 4
- 2 3 2 2
- 3 4 2 5
- */
- #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(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);
- }
- int L = 1000000000;
- for (int i = 29; i >= 0; -- i) {
- int to = L - (1ll << i);
- init_visited();
- if (reachable(s, to)) L = to;
- }
- init_visited();
- 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;
- // sd[v] = upcoming.begin()->first;
- upcoming.erase(upcoming.begin());
- // visited[v] = true;
- for(size_t i = 0; i < nei[v].size(); ++i){
- if(dan[v][i] > L) continue;
- int v2 = nei[v][i];
- // if(visited[v2]) continue;
- // 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