Submission #1266925

#TimeUsernameProblemLanguageResultExecution timeMemory
1266925VKhangCommuter Pass (JOI18_commuter_pass)C++20
100 / 100
208 ms79400 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5, MOD = 1e9 + 7; const long long L = 1e18; #define ll long long #define fi first #define se second #define yes {cout << "YES";return;} #define no {cout << "NO"; return;} #define pb push_back #define MASK(i) (1ll << (i)) #define BIT(i, s) ((1ll << (i)) & (s)) #define all(a) a.begin(), a.end() int n, m, s, t, u, v; ll dist[N][4]; bool visited[N]; vector <pair <int, int>> adj[N]; int a[4]; priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater <pair <ll, int>>> p; bool minimize(ll &x, const ll y){ if (x > y){ x = y; return true; } return false; } void dijkstra(int id){ memset(visited, false, sizeof visited); dist[a[id]][id] = 0; p.push({0, a[id]}); while(p.size()){ ll i = p.top().fi; int j = p.top().se; p.pop(); if (visited[j]) continue; visited[j] = true; for (auto x: adj[j]){ if (minimize(dist[x.fi][id], i + x.se)){ p.push({dist[x.fi][id], x.fi}); } } } } ll res; ll ans = 1e18; ll f[N][2]; void solve() { cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; i++){ int x, y, w; cin >> x >> y >> w; adj[x].pb({y, w}); adj[y].pb({x, w}); } memset(dist, 0x3f, sizeof dist); a[0] = s; a[1] = t; a[2] = u; a[3] = v; dijkstra(0); dijkstra(1); dijkstra(2); dijkstra(3); res = dist[t][0]; memset(f, 0x3f, sizeof f); memset(visited, false, sizeof visited); p.push({0, s}); ans = dist[v][2]; while(p.size()){ ll i = p.top().fi; int j = p.top().se; p.pop(); if (visited[j]) continue; visited[j] = true; f[j][0] = min(f[j][0], dist[j][2]); f[j][1] = min(f[j][1], dist[j][3]); ans = min(ans, f[j][0] + dist[j][3]); ans = min(ans, f[j][1] + dist[j][2]); for (auto x: adj[j]){ if (i + x.se + dist[x.fi][1] == res){ f[x.fi][0] = min(f[x.fi][0], f[j][0]); f[x.fi][1] = min(f[x.fi][1], f[j][1]); p.push({dist[x.fi][0], x.fi}); } } } cout << ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); if (fopen("VKhang.inp","r")){ freopen("VKhang.inp","r",stdin); freopen("VKhang.out","w",stdout); } solve(); return 0; }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("VKhang.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("VKhang.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...