제출 #854791

#제출 시각아이디문제언어결과실행 시간메모리
854791hungntCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
201 ms26180 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<long long, int> const int N = 1e9 + 7; using namespace std; //khai bao int n, m, s, t, x, y; vector<pii> ke[100009]; // dijkstra priority_queue<pii, vector<pii>, greater<pii> > p; ll f[100009][2]; pair<ll, ll> g[100009]; ll dijkstra(int s, int t, int id){ while(p.size()) p.pop(); for(int i = 0; i <= n; i ++) f[i][id] = 1e18; f[s][id] = 0; p.push({0, s}); while(p.size()){ pii o = p.top(); p.pop(); if(f[o.second][id] != o.first) continue; if(o.second == t) return o.first; for(pii i : ke[o.second]) if(f[i.second][id] > o.first + i.first){ f[i.second][id] = o.first + i.first; p.push({f[i.second][id], i.second}); } } return 0; } /// tinh toan struct kt{ ll w, w1, w2, u; }; struct sx{ bool operator()(kt a, kt b){ if(a.w == b.w) return (a.w2 + a.w1) > (b.w2 + b.w1); return a.w > b.w; } }; priority_queue<kt, vector<kt>, sx> q; ll tinh(){ for(int i = 1; i <= n; i ++) g[i] = {1e18, 1e18}; q.push({0, f[s][0], f[s][1], s}); g[s] = {0, f[s][0] + f[s][1]}; while(q.size()){ kt o = q.top(); // cout << o.u << " " << o.w << " " << o.w1 << " " << o.w2 << '\n'; q.pop(); if(o.u == t) return o.w1 + o.w2; pair<ll, ll> y; y = {o.w, o.w1 + o.w2}; if(g[o.u] != y) continue; for(pii i : ke[o.u]){ y = {o.w + i.first, min(o.w1, f[i.second][0]) + min(o.w2, f[i.second][1])}; if(g[i.second] > y){ g[i.second] = {o.w + i.first, min(o.w1, f[i.second][0]) + min(o.w2, f[i.second][1])}; q.push({g[i.second].first, min(o.w1, f[i.second][0]), min(o.w2, f[i.second][1]), i.second}); } } } return 2; } /// main mannnnnnnn int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("bus.inp", "r", stdin); //freopen("bus.out", "w", stdout); cin >> n >> m >> s >> t >> x >> y; int u, v, w; while(m --){ cin >> u >> v >> w; ke[u].push_back({w, v}); ke[v].push_back({w, u}); } ll res = dijkstra(x, y, 0); ll l = dijkstra(x, 0, 0); l = dijkstra(y, 0, 1); res = min(res, tinh()); cout << res; } //8 8 //1 6 //3 8 //1 2 3 //2 4 2 //2 3 3 //4 5 3 //3 5 2 //5 6 3 //2 7 4 //8 2 3

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:80:8: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   80 |     ll l = dijkstra(x, 0, 0);
      |        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...