Submission #1008951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008951		devariaota	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	458 ms	27328 KiB

commuter_pass

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
vector<int>adj[100005];
int par[100005];
int dist[100005];
bool vis[100005];
signed main()
{
  int n, m, s, t, u, v;map<pair<int, int>, int> mp;
  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;
  }
  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]=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], now), max(par[now], now)}]=0;
    now=par[now];
  }
  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:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%lld %lld %lld %lld %lld %lld", &n, &m, &s, &t, &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%lld %lld %lld", &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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