Submission #81041

#TimeUsernameProblemLanguageResultExecution timeMemory
81041farukkastamonudaCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
807 ms150560 KiB
#include <bits/stdc++.h> #define fi first #define se second #define lo long long #define inf 1000000000000000000 #define md 1000000007 #define li 100005 #define mp make_pair #define pb push_back #define pi pair<lo int, int> using namespace std; int n, m, s, t, u, v, x, y; lo int vis[li], du[li], dv[li], ans = inf, z; lo int tu[li], tv[li]; vector< pair<int, lo int> > vv[li]; struct node{ lo int val; int cit; lo int mnu, mnv; }; bool operator < (node a, node b){ if(a.val == b.val){ if(a.mnu == b.mnu) return a.mnv > b.mnv; return a.mnu > b.mnu; } return a.val > b.val; } void sp(){ for(int i = 1; i <= n; i ++){ vis[i] = inf; tu[i] = inf; tv[i] = inf; } priority_queue<node> q; q.push((node){0, s, du[s], dv[s]}); while(! q.empty()){ node temp = q.top(); q.pop(); lo int cst = temp.val; int seh = temp.cit; lo int uya = temp.mnu; lo int vye = temp.mnv; if(vis[seh] < cst) continue; if(vis[seh] == cst && tu[seh] <= uya && tv[seh] <= vye) continue; vis[seh] = cst; tu[seh] = min(tu[seh], uya); tv[seh] = min(tv[seh], vye); if(seh == t){ //printf("debug-> :: %d %d %d\n", uya, vye, seh); ans = min(ans , uya + vye); } for(int i = 0; i < (int)vv[seh].size() ; i ++){ int go = vv[seh][i].fi; lo int knr = vv[seh][i].se; q.push((node){cst + knr, go, min(uya, du[go]), min(vye, dv[go])}); } } } void bfsu(){ priority_queue< pair<lo int, int> > q; q.push(mp(0, u)); while(!q.empty()){ pi temp = q.top(); q.pop(); int seh = temp.se; lo int val = - temp.fi; if(vis[seh] == 1 ) continue; vis[seh] = 1; du[seh] = val; for(int i = 0; i < (int)vv[seh].size(); i ++){ int go = vv[seh][i].fi; lo int knr = vv[seh][i].se; q.push(mp(- val - knr, go)); } } memset(vis, 0 , sizeof(vis)); } void bfsv(){ priority_queue< pair<lo int, int> > q; q.push(mp(0, v)); while(!q.empty()){ pi temp = q.top(); q.pop(); int seh = temp.se; lo int val = - temp.fi; if(vis[seh] == 1 ) continue; vis[seh] = 1; dv[seh] = val; for(int i = 0; i < (int)vv[seh].size(); i ++){ int go = vv[seh][i].fi; lo int knr = vv[seh][i].se; q.push(mp(- val - knr, go)); } } memset(vis, 0 , sizeof(vis)); } int main(){ scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u ,&v); for(int i = 1; i <= m ; i ++){ scanf("%d %d %lld", &x, &y, &z); vv[x].pb(mp(y, z)); vv[y].pb(mp(x, z)); } bfsu(); bfsv(); sp(); printf("%lld\n", min(ans, du[v])); return 0; }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u ,&v);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...