제출 #500093

#제출 시각아이디문제언어결과실행 시간메모리
500093aSSSdCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
334 ms23128 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r) { return l+rng()%(r-l+1); } #define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define forinc(x,a,b) for(int x=a;x<=b;x++) #define fordec(x,a,b) for(int x=a;x>=b;x--) #define iii pair<ii,int> #define fi first #define se second #define pb push_back #define ll long long #define ii pair<int,int> #define mt make_tuple #define getbit(x,i) ((x>>(i))&1) #define batbit(x,i) (x|(1ll<<(i))) #define tatbit(x,i) (x&~(1<<(i))) #define endl '\n' #define all(v) v.begin(), v.end() #define gg exit(0); #define int long long const int N = 1e5 + 1000; int n,m; vector<ii> ke[N]; int s, t, u, v; vector<int> ditcha(int st) { vector<int> d(n+1,1e16); priority_queue<ii, vector<ii>, greater<ii> > q; q.push({0, st}); d[st] =0; while(!q.empty()) { ii u = q.top(); q.pop(); if(u.fi != d[u.se]) continue; for(auto v : ke[u.se]) { int cost = v.se; if(d[v.fi] > d[u.se] + v.se) { d[v.fi] = d[u.se] + v.se; q.push({d[v.fi], v.fi}); } } } return d; } int f[N], dp[N]; main() { // freopen("task.inp" , "r" , stdin); fasty; cin >> n >> m; cin >> s >> t; cin >> u >> v; forinc(i,1,m) { int u, v, c; cin >> u >> v >>c; ke[u].pb({v,c}); ke[v].pb({u,c}); } vector<int> ds = ditcha(s); vector<int> dt = ditcha(t); vector<int> du = ditcha(u); vector<int> dv = ditcha(v); //cout << du[v] << "\n"; // cout << du[s] << "\n"; int res = 1e18; for(int _ = 0 ; _ < 2 ; _++) { priority_queue<ii, vector<ii>, greater<ii> > q; forinc(i,0,n+1) dp[i] = 1e16; forinc(i,0,n+1) f[i] = 1e16; f[s]=0; dp[s] = du[s]; //cout << dp[s] << " "; q.push({0,s}); while(!q.empty()) { ii u = q.top(); q.pop(); if(f[u.se] != u.fi) continue; //u - i //cout << dp[u.se] + dv[u.se] << "\n"; //cout << u.se << " " << dp[u.se] << " " << dv[u.se] << "\n"; //gg; res = min(res, dp[u.se] + dv[u.se]); //cout << res << " "; // s ----- u ------ v ----- t for(auto v : ke[u.se]) { if(ds[v.fi] + dt[v.fi] == ds[t] ) { dp[v.fi] = min({dp[v.fi] , dp[u.se] , du[u.se]} ); if(f[v.fi] > v.se + f[u.se]) { f[v.fi] = v.se + f[u.se]; q.push({f[v.fi], v.fi}); } } } } //cout << "co swap ko >> "; swap(du,dv); } // cout << res << "\n"; res = min(res , du[v]); cout << res; }

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

commuter_pass.cpp: In function 'std::vector<long long int> ditcha(long long int)':
commuter_pass.cpp:42:17: warning: unused variable 'cost' [-Wunused-variable]
   42 |             int cost = v.se;
      |                 ^~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...