Submission #61852

#TimeUsernameProblemLanguageResultExecution timeMemory
61852kingpig9Commuter Pass (JOI18_commuter_pass)C++11
100 / 100
982 ms83172 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, int> edge; const int MAXN = 100010; const ll INF = 0x0101010101010101; //#define debug(...) fprintf(stderr, __VA_ARGS__) #define debug(...) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) void setmin (ll &a, ll b) { if (a > b) { a = b; } } int N, M, S, T, U, V; vector<edge> adj[MAXN]; ll sdist[MAXN], tdist[MAXN], udist[MAXN], vdist[MAXN]; bool vis[MAXN]; void dijkstra (ll *dist, int s) { fill_n(dist + 1, N, INF); fill_n(vis + 1, N, false); dist[s] = 0; priority_queue<edge, vector<edge>, greater<edge>> pq; pq.emplace(0ll, s); while (!pq.empty()) { int u = pq.top().se; ll w = pq.top().fi; pq.pop(); if (vis[u]) { continue; } vis[u] = true; for (edge e : adj[u]) { ll nw = w + e.fi; int v = e.se; if (nw < dist[v]) { dist[v] = nw; pq.emplace(nw, v); } } } } ll dp[MAXN]; vector<int> dag[MAXN]; ll getdp (int x) { ll &ref = dp[x]; if (ref != INF) { return ref; } ref = vdist[x]; for (int y : dag[x]) { setmin(ref, getdp(y)); } return ref; } ll go() { debug("---------PROPAGANDA--------\n"); #warning reset EVERYTHING! dijkstra(sdist, S); dijkstra(tdist, T); dijkstra(udist, U); dijkstra(vdist, V); //now start the work - calc SP dag //U -> vertex -> somewhere in sub of vertex -> V fillchar(dp, 1); for (int i = 1; i <= N; i++) { dag[i].clear(); for (edge e : adj[i]) { int j = e.se; //S -> i -> j -> T if (sdist[i] + e.fi + tdist[j] == sdist[T]) { debug("%d -> %d\n", i, j); dag[i].push_back(j); } } } ll ans = udist[V]; for (int i = 1; i <= N; i++) { setmin(ans, udist[i] + getdp(i)); } return ans; } int main() { scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V); for (int i = 1; i <= M; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); adj[a].emplace_back(c, b); adj[b].emplace_back(c, a); } ll ans = INF; for (int qi = 0; qi < 2; qi++) { swap(U, V); setmin(ans, go()); } printf("%lld\n", ans); }

Compilation message (stderr)

commuter_pass.cpp:73:2: warning: #warning reset EVERYTHING! [-Wcpp]
 #warning reset EVERYTHING!
  ^~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:103: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:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...