제출 #1087820

#제출 시각아이디문제언어결과실행 시간메모리
1087820JanPhamCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
2071 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define TranLeThanhTam "TranLeThanhTam" #define all(v) v.begin(),v.end() #define reset(a,i) memset(a,i,sizeof(a)) #define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i,a,b) for (int i = (a), _b = (b); i >= _b; --i) #define compact(v) sort(all(v)), v.erase(unique(all(v)), end(v)) #define sz(v) (int) v.size() #define MASK(i) (1 << (i)) typedef long long ll; typedef long double lb; typedef pair<ll,ll> pll; typedef pair<int,int> pii; const int Thanh_Tam = 1e5 + 17; const int inf = 1e9 + 17; const long long infll = 1e18 + 17; const int MOD = 1e9 + 7; const int Log = 17; const int dx[4] = {-1, 0, 0, 1}; const int dy[4] = {0, -1, 1, 0}; const int max_block_size = 270; const ll P = 311; const int maxA = 1e6 + 17; const int addi = 1e9; const char dir[4] = {'W', 'S', 'N', 'E'}; const int Mod[3] = {998244353, MOD, 759186269}; ll mul(ll a, ll b, ll mod); ll binpow(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1) res = mul(res,a,mod); b >>= 1; a = mul(a,a,mod); } return res; } ll add(ll a, ll b, ll mod) { return (a + b) % mod; } ll sub(ll a, ll b, ll mod) { return (a - b + mod) % mod; } ll mul(ll a, ll b, ll mod) { return ((a % mod) * (b % mod)) % mod; } ll div(ll a, ll b, ll mod) { return mul(a, binpow(b, mod - 2, mod), mod); } mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rand_range(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);} int n,m,S,T,U,V; ll distS[Thanh_Tam], distT[Thanh_Tam], distU[Thanh_Tam], distV[Thanh_Tam]; vector<pii> adj[Thanh_Tam]; void bfs(int x, ll dis[]) { priority_queue<pll> pq; pq.push({x,0}); FOR(i,1,n) dis[i] = infll; while (!pq.empty()) { int u = pq.top().fi; ll val = pq.top().se; pq.pop(); if (dis[u] < val) continue; dis[u] = val; for (pll v : adj[u]) pq.push({v.fi, v.se + dis[u]}); } return; } ll dp[2][Thanh_Tam], best = 4e18; bool vis[Thanh_Tam]; void dfs(int u) { vis[u] = true; dp[0][u] = dp[1][u] = 4e18; for (pll v: adj[u]) { if (distS[u] + distT[v.fi] + v.se != distS[T]) continue; if (!vis[v.fi]) dfs(v.fi); dp[0][u] = min(dp[0][u], dp[0][v.fi]); dp[1][u] = min(dp[1][u], dp[1][v.fi]); } best = min(best, distU[u] + dp[1][u]); best = min(best, distV[u] + dp[0][u]); dp[0][u] = min(dp[0][u], distU[u]); dp[1][u] = min(dp[1][u], distV[u]); return; } void ThanhTam() { cin >> n >> m >> S >> T >> U >> V; FOR(i,1,m) { int u,v,w; cin >> u >> v >> w; adj[u].pb({v,w}); adj[v].pb({u,w}); } bfs(S, distS); bfs(T, distT); bfs(U, distU); bfs(V, distV); best = distV[U]; dfs(S); cout << best; return; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if (fopen(TranLeThanhTam".inp","r")) { freopen(TranLeThanhTam".inp","r",stdin); freopen(TranLeThanhTam".out","w",stdout); } int t = 1; //cin >> t; while (t--) ThanhTam(); return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(TranLeThanhTam".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(TranLeThanhTam".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...