Submission #316289

#	Time	Username	Problem	Language	Result	Execution time	Memory
316289		tushar_2658	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	494 ms	31956 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;

const int maxn = 100005;
using ll = long long;

vector<pair<int, ll>> edges[maxn];
ll dis[3][maxn];
vector<int> g[maxn], rg[maxn];
int n, m;

void dijkstra(int id, int s){
  memset(dis[id], 63, sizeof dis[id]);
  dis[id][s] = 0;
  using pii = pair<ll, int>;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  pq.push({0, s});
  vector<int> vis(n + 1);
  while(!pq.empty()){
    pii src = pq.top();
    pq.pop();
    if(vis[src.second])continue;
    vis[src.second] = 1;
    for(auto i : edges[src.second]){
      ll cost = dis[id][src.second] + i.second;
      if(dis[id][i.first] > cost){
        dis[id][i.first] = cost;
        pq.push({cost, i.first});
      }
    }
  }
}

ll dp[2][maxn];
int vis[maxn], deg[maxn];
vector<int> order;

void dfs(int x){
  vis[x] = 1; 
  for(auto i : g[x]){
    if(!vis[i]){
      dfs(i);
    }
  }
  order.push_back(x);
}

int main(int argc, char const *argv[])
{
  scanf("%d %d", &n, &m);
  int s, t, u, v;
  scanf("%d %d", &s, &t);
  scanf("%d %d", &u, &v);
  for(int i = 0; i < m; ++i){
    int x, y;
    ll c;
    scanf("%d %d %lld", &x, &y, &c);
    edges[x].push_back({y, c});
    edges[y].push_back({x, c});
  }
  dijkstra(0, s);
  dijkstra(1, u);
  dijkstra(2, v);
  queue<int> q;
  q.push(t);
  vector<int> vis(n + 1);
  while(!q.empty()){
    int src = q.front();
    q.pop(); 
    if(vis[src])continue;
    vis[src] = 1;
    for(auto i : edges[src]){
      ll cost = dis[0][i.first] + i.second;
      if(dis[0][src] == cost){
        g[i.first].push_back(src);
        deg[src]++;
        q.push(i.first);
      }
    }
  }
  dfs(s);
  ll ans = dis[1][v];
  for(auto i : order){
    dp[0][i] = dis[1][i];
    dp[1][i] = dis[2][i];
    for(auto j : g[i]){
      dp[0][i] = min(dp[0][i], dp[0][j]);
      dp[1][i] = min(dp[1][i], dp[1][j]);
    }
    ans = min(ans, dis[1][i] + dp[1][i]);
    ans = min(ans, dis[2][i] + dp[0][i]);
  }
  cout << ans << endl;

  return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main(int, const char**)':
commuter_pass.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d %d", &s, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d %d %lld", &x, &y, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45