Submission #1008988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008988		devariaota	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	697 ms	31056 KiB

commuter_pass

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
vector<int>adj[100005], par[100005];
int dist[100005], distx[100005], ans=1e18;
bool vis[100005];
int n, m, s, t, u, v;map<pair<int, int>, int> mp;
void dfs(int node)
{
  ans=min(ans, distx[node]);
//  printf("%lld %lld %lld %lld\n", node, dist[v], dist[node], distx[node]);
  for(auto x:par[node])
  {
    if(!vis[x])
    {
      vis[x]=1;
      dfs(x);
    }
  }
}
signed main()
{
  scanf("%lld %lld %lld %lld %lld %lld", &n, &m, &s, &t, &u, &v);
  for(int i=1; i<=m; i++)
  {
    int a, b, c;
    scanf("%lld %lld %lld", &a, &b, &c);
    if(a>b)swap(a, b);
    adj[a].push_back(b);
    adj[b].push_back(a);
    mp[{a, b}]=c;
  }
  if(s==u)
  {
    priority_queue<pair<int, int> > pq;
    pq.push({0, s});
    for(int i=1; i<=n; i++)
    {
      dist[i]=1e18;
      distx[i]=1e18;
    }
    dist[s]=0;
    while(!pq.empty())
    {
      int step=-pq.top().fi;
      int node=pq.top().se;
  //    int p=pq.top().se.se;
  //    par[node].push_back(p);
      pq.pop();
      if(vis[node])
      {
        continue;
      }
      vis[node]=1;
      for(auto x:adj[node])
      {
        if(dist[x]==step+mp[{min(node, x), max(node, x)}])
        {
          par[x].push_back(node);
        }
        else if(dist[x]>step+mp[{min(node, x), max(node, x)}])
        {
          par[x].clear();
          par[x].push_back(node);
          dist[x]=step+mp[{min(node, x), max(node, x)}];
          pq.push({-(step+mp[{min(node, x), max(node, x)}]), x});
        }
      }
    }
    for(int i=1; i<=n; i++)vis[i]=0;
    distx[v]=0;
    pq.push({0, v});
    while(!pq.empty())
    {
      int step=-pq.top().fi;
      int node=pq.top().se;
  //    int p=pq.top().se.se;
  //    par[node].push_back(p);
      pq.pop();
      if(vis[node])
      {
        continue;
      }
      vis[node]=1;
      for(auto x:adj[node])
      {
        if(distx[x]>step+mp[{min(node, x), max(node, x)}])
        {
          distx[x]=step+mp[{min(node, x), max(node, x)}];
          pq.push({-(step+mp[{min(node, x), max(node, x)}]), x});
        }
      }
    }
    for(int i=1; i<=n; i++)vis[i]=0;
    ans=distx[u];
    vis[t]=1;
    dfs(t);
    printf("%lld\n", ans);
  }
  else
  {
    priority_queue<pair<int, int> > pq;
    pq.push({0, s});
    for(int i=1; i<=n; i++)dist[i]=1e18;
    dist[s]=0;
    while(!pq.empty())
    {
      int step=-pq.top().fi;
      int node=pq.top().se;
  //    int p=pq.top().se.se;
  //    par[node].push_back(p);
      pq.pop();
      if(vis[node])
      {
        continue;
      }
      vis[node]=1;
      for(auto x:adj[node])
      {
        if(dist[x]==step+mp[{min(node, x), max(node, x)}])
        {
          par[x].push_back(node);
        }
        else if(dist[x]>step+mp[{min(node, x), max(node, x)}])
        {
          par[x].clear();
          par[x].push_back(node);
          dist[x]=step+mp[{min(node, x), max(node, x)}];
          pq.push({-(step+mp[{min(node, x), max(node, x)}]), x});
        }
      }
    }
    int now=t;
    while(now!=s)
    {
  //    printf("%lld\n", now);
      mp[{min(par[now][0], now), max(par[now][0], now)}]=0;
      now=par[now][0];
    }
    for(int i=1; i<=n; i++)
    {
  //    printf("%lld\n", i);
      vis[i]=0;
      dist[i]=1e18;
    }
    dist[u]=0;
    priority_queue<pair<int, int> > q;q.push({0, u});
    while(!q.empty())
    {
      int step=-q.top().fi;
      int node=q.top().se;
      q.pop();
      if(vis[node])
      {
        continue;
      }
      vis[node]=1;
      for(auto x:adj[node])
      {
        if(dist[x]>step+mp[{min(node, x), max(node, x)}])
        {
          dist[x]=step+mp[{min(node, x), max(node, x)}];
          q.push({-(step+mp[{min(node, x), max(node, x)}]), x});
        }
      }
    }
    printf("%lld\n", dist[v]);  
  }
}

Compilation message (stderr)

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

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