제출 #765461

#제출 시각아이디문제언어결과실행 시간메모리
765461wmureeCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
313 ms21540 KiB
/* Muqalzhar taui */ #include <bits/stdc++.h> #include <iomanip> #define ll long long #define pb push_back #define F first #define S second #define nl '\n' #define all(x) x.begin(), x.end() const int N = 2e5 + 7; const int modd = 1e9 + 7; const int INF = 1e9 + 7; const double pi = 3.141592653589793238462643383279502884197; const double EPS = 0.0000000000001; using namespace std; int gcd(int a, int b){ if (b == 0) return a; else return gcd(b, a % b); } ll binpow(ll a, ll x){ if(x == 0) return 1; if(x % 2 == 0){ ll y = binpow(a, x / 2); return (y * y); } else{ return (binpow(a, x - 1) * a); } } ll n, m, s, t, u, v; vector <pair <ll, ll>> e[N]; ll dpu[N]; ll dpv[N]; ll du[N]; ll dv[N]; void Muqaltin(){ cin >> n >> m >> s >> t >> u >> v; for(int i = 1; i <= m; i++){ ll a,b,c; cin >> a >> b >> c; e[a].pb({b, c}); e[b].pb({a, c}); } for(int i = 1; i <= n; i++){ du[i] = INF; dv[i] = INF; dpu[i] = INF; dpv[i] = INF; } set <pair <ll, ll>> q; dv[t] = 0; q.insert({dv[t], t}); while(!q.empty()){ ll x = q.begin()->second; q.erase(q.begin()); for(auto to : e[x]){ if(dv[to.F] > dv[x] + to.S){ q.erase({dv[to.F], to.F}); dv[to.F] = dv[x] + to.S; q.insert({dv[to.F], to.F}); } } } du[s] = 0; q.insert({du[s], s}); ll par = 0; while(!q.empty()){ ll x = q.begin()->second; q.erase(q.begin()); for(auto to : e[x]){ if(du[to.F] > du[x] + to.S){ q.erase({du[to.F], to.F}); du[to.F] = du[x] + to.S; q.insert({du[to.F], to.F}); } } } set <pair <ll, ll>> st; dpu[u] = 0; st.insert({dpu[u], u}); while(!st.empty()){ ll x = st.begin()->second; st.erase(st.begin()); for(auto to : e[x]){ if(du[x] + to.S + dv[to.F] != du[t]){ if(dpu[to.F] > dpu[x] + to.S){ st.erase({dpu[to.F], to.F}); dpu[to.F] = dpu[x] + to.S; st.insert({dpu[to.F], to.F}); } } else{ if(dpu[to.F] > dpu[x]){ st.erase({dpu[to.F], to.F}); dpu[to.F] = dpu[x]; st.insert({dpu[to.F], to.F}); } } } } // dpv[u] = 0; // st.insert({dpu[u], u}); // while(!st.empty()){ // ll x = st.begin()->second; // st.erase(st.begin()); // for(auto to : e[x]){ // if(du[x] + to.S + dv[to.F] != du[t]){ // if(dpu[to.F] > dpu[x] + to.S){ // st.erase({dpu[to.F], to.F}); // dpu[to.F] = dpu[x] + to.S; // st.insert({dpu[to.F], to.F}); // } // } // else{ // if(dpu[to.F] > dpu[x]){ // st.erase({dpu[to.F], to.F}); // dpu[to.F] = dpu[x]; // st.insert({dpu[to.F], to.F}); // } // } // } // } cout << dpu[v]; return; } int main(){ // freopen("pails.in", "r", stdin); // freopen("pails.out", "w", stdout); ios_base :: sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while(t--){ Muqaltin(); } return 0; }

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

commuter_pass.cpp: In function 'void Muqaltin()':
commuter_pass.cpp:76:8: warning: unused variable 'par' [-Wunused-variable]
   76 |     ll par = 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...