제출 #788576

#제출 시각아이디문제언어결과실행 시간메모리
788576ooscodeCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
361 ms41548 KiB
// IN THE NAME OF ALLAH #include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(false);cin.tie(NULL) #define wall cerr << "------------------------------------" << endl #define pb push_back #define pob pop_back #define F first #define S second #define all(x) x.begin() , x.end() #define scan scanf #define print printf #define outs(x) print("%lld " , x) #define out(x) print("%lld\n" , x) #define in(x) scan("%lld" , &x) #define int ll #define kids int tm = (tl + tr)/2; int cl = 2*v; int cr = 2*v+1 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #pragma GCC optimize("Ofast") typedef long long ll; typedef pair<int , int> pii; typedef pair<ll , ll> pll; typedef pair<pii,int> piii; typedef pair<pll , ll> plll; const int N = 1e5+10; const int K = 70+10; const ll mod = 998244353; const ll INF = 1e18+10; const int P = 31; const int lg = 25; vector<pii> g[N]; vector<pii> gr[N]; vector<pii> rg[N]; int dp[N]; int pd[N]; int n , m; int s , t; int x , y; int dis[5][N]; int mark[N]; pair<pii , int> edg[2*N]; vector<int> vec , ve; void dfs(int v) { mark[v] = 1; for(auto u : gr[v]) if(!mark[u.F]) dfs(u.F); vec.pb(v); } void topol() { for(int i = 1 ; i <= ve.size() ; i++) if(!mark[ve[i-1]]) dfs(ve[i-1]); reverse(all(vec)); } void dij(int v , int t) { priority_queue<pii , vector<pii> , greater<pii>> pq; dis[t][v] = 0; pq.push({0 , v}); while(pq.size()) { int v = pq.top().S; int ww = pq.top().F; pq.pop(); if(ww != dis[t][v]) continue; for(auto u : g[v]) if(dis[t][u.F] > dis[t][v] + u.S) { dis[t][u.F] = dis[t][v] + u.S; pq.push({dis[t][u.F] , u.F}); } } } void solve() { cin >> n >> m >> s >> t >> x >> y; for(int i = 1 ; i <= m ; i++) { int v , u , w; cin >> v >> u >> w; g[v].pb({u , w}); g[u].pb({v , w}); edg[i] = {{v , u} , w}; } for(int i = 1 ; i <= 4 ; i++) for(int j = 1 ; j <= n ; j++) dis[i][j] = INF; dij(s , 1); dij(t , 2); dij(x , 3); dij(y , 4); for(int i = 1 ; i <= m ; i++) { int v = edg[i].F.F; int u = edg[i].F.S; int w = edg[i].S; if(dis[1][v] + w + dis[2][u] == dis[1][t]) { gr[v].pb({u , w}); rg[u].pb({v , w}); if(!mark[v]) { mark[v] = 1; ve.pb(v); } if(!mark[u]) { mark[u] = 1; ve.pb(u); } } if(dis[1][u] + w + dis[2][v] == dis[1][t]) { gr[u].pb({v , w}); rg[v].pb({u , w}); if(!mark[v]) { mark[v] = 1; ve.pb(v); } if(!mark[u]) { mark[u] = 1; ve.pb(u); } } } for(int i = 1 ; i <= n ; i++) mark[i] = 0; topol(); int ans = INF; for(auto v : vec) { dp[v] = dis[3][v]; for(auto u : rg[v]) dp[v] = min(dp[v] , dp[u.F]); ans = min(ans , dp[v] + dis[4][v]); } for(int i = vec.size()-1 ; i >= 0 ; i--) { int v = vec[i]; pd[v] = dis[3][v]; for(auto u : gr[v]) pd[v] = min(pd[v] , pd[u.F]); ans = min(ans , pd[v] + dis[4][v]); } cout << min(ans , dis[3][y]) << "\n"; } signed main() { int n = 1; // cin >> n; while(n--) solve(); } // CODE = LOVE // IT'S EASY TO SEE

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

commuter_pass.cpp: In function 'void topol()':
commuter_pass.cpp:67:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 1 ; i <= ve.size() ; i++)
      |                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...