Submission #857440

#TimeUsernameProblemLanguageResultExecution timeMemory
857440asdasdqwerCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
299 ms32136 KiB
// #define FMT_HEADER_ONLY // #include <fmt/ranges.h> #include <bits/stdc++.h> using namespace std; #define int int64_t #define pii pair<int, int> vector<int> dijkstra(int source, vector<vector<pii>> &g) { int n = g.size(); vector<int> dis(n, 1e16); dis[source] = 0; priority_queue<pii> pq; for (int i=0;i<n;i++) { pq.push({-dis[i], i}); } vector<bool> vis(n, false); while (!pq.empty()) { pii t = pq.top();pq.pop(); int node = t.second; if (vis[node]) continue; vis[node] = true; for (pii &x:g[node]) { if (dis[node] + x.second < dis[x.first]) { dis[x.first] = dis[node] + x.second; pq.push({-dis[x.first], x.first}); } } } return dis; } void dfs(int node, vector<int> &vis, vector<int> &topo, vector<vector<int>> &g) { vis[node] = 1; for (int x:g[node]) { if (vis[x] == 0) { dfs(x, vis, topo, g); } } vis[node] = 2; topo.push_back(node); } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, m;cin>>n>>m; int s, t;cin>>s>>t;s--;t--; int u, v;cin>>u>>v;u--;v--; vector<vector<pii>> g(n); for (int i=0;i<m;i++) { int a, b, c;cin>>a>>b>>c; a--;b--; g[a].push_back({b, c}); g[b].push_back({a, c}); } vector<int> disFromS = dijkstra(s, g); vector<vector<int>> dag(n); queue<int> q; q.push(t); vector<bool> proc(n, false); proc[t] = true; while (!q.empty()) { int tp = q.front();q.pop(); for (pii &x:g[tp]) { if (disFromS[tp] == disFromS[x.first] + x.second) { dag[x.first].push_back(tp); if (!proc[x.first]) { proc[x.first] = true; q.push(x.first); } } } } vector<int> vis(n, 0), topo; for (int i=0;i<n;i++) { if (vis[i] == 0 && dag[i].size()) { dfs(i, vis, topo, dag); } } reverse(topo.begin(), topo.end()); vector<int> disToU = dijkstra(u, g), disToV = dijkstra(v, g); int mn = disToV[u]; vector<int> minGet(n, 1e16); for (int i=0;i<topo.size();i++) { int elem = topo[i]; if (i == 0) { minGet[elem] = disToU[elem]; mn = min(mn, minGet[elem] + disToV[elem]); } mn = min(mn, minGet[elem] + disToV[elem]); for (int x:dag[elem]) { minGet[x] = min(minGet[x], min(minGet[elem], disToU[x])); mn = min(mn, minGet[x] + disToV[x]); } } vector<vector<int>> rev(n); for (int i=0;i<n;i++) { for (int x:dag[i]) { rev[x].push_back(i); } } vis = vector<int>(n, 0); vector<int> newTopo; for (int i=0;i<n;i++) { if (vis[i] == 0 && rev[i].size()) { dfs(i, vis, newTopo, rev); } } minGet = vector<int>(n, 1e16); // cerr << (newTopo[0] == t) << "\n"; // fmt::print("{}\n", newTopo); reverse(newTopo.begin(), newTopo.end()); for (int i=0;i<(int)newTopo.size();i++) { int elem = newTopo[i]; if (i == 0) { minGet[elem] = disToU[elem]; } mn = min(mn, minGet[elem] + disToV[elem]); for (int x:rev[elem]) { minGet[x] = min(minGet[x], min(minGet[elem], disToU[x])); mn = min(mn, minGet[x] + disToV[x]); } } cout << mn << "\n"; }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i=0;i<topo.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...