Submission #1091935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091935		vu28082007	Robot (JOI21_ho_t4)	C++14	100 / 100	117 ms	31172 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define taskname ""
#define ll long long 
#define fi first
#define se second
#define pb push_back

const int N = 2e5+7;
ll n, m, dist[N], sum[N], save[N], dem[N], a, b, c, p;
vector<array<ll,3>> adj[N];
bool vs[N];
priority_queue<array<ll,2>, vector<array<ll,2>>, greater<array<ll,2>>> pq;
void mvu()
{
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
  {
    cin >> a >> b >> c >> p;
    adj[a].pb({b,c,p});
    adj[b].pb({a,c,p});
  }
  for (int i = 1; i <= n; i++)
  {
    vs[i]=0;
    dist[i]=1e18;
  }
  dist[1]=0;
  pq.push({0,1});
  while(!pq.empty())
  {
    auto k = pq.top();
    pq.pop();
    if(vs[k[1]]) continue;
    vs[k[1]]=1;
    for (auto e : adj[k[1]])
    {
      sum[e[1]]=0;
      dem[e[1]]=0;
      save[e[1]]=1e18;
    }
    for (auto e : adj[k[1]])
    {
      sum[e[1]]+=e[2];
      dem[e[1]]++;
      save[e[1]]=min(save[e[1]], dist[e[0]]);
    }
    for (auto e : adj[k[1]])
    {
      if(dem[e[1]]==1)
      {
        if(dist[e[0]] > dist[k[1]])
        {
          dist[e[0]]=dist[k[1]];
          pq.push({dist[e[0]], e[0]});
        }
      }
      else
      {
        if(dist[e[0]] > dist[k[1]]+min(sum[e[1]]-e[2], e[2]))
        {
          dist[e[0]]=dist[k[1]]+min(sum[e[1]]-e[2], e[2]);
          pq.push({dist[e[0]], e[0]});
        }
      }
      if(dist[e[0]] > save[e[1]]+sum[e[1]]-e[2])
      {
        dist[e[0]]=save[e[1]]+sum[e[1]]-e[2];
        pq.push({dist[e[0]], e[0]});
      }
    }
  }
  if(dist[n]==1e18) cout << -1;
  else cout << dist[n];
}

int main()
{
  if(fopen(taskname".inp", "r"))
  {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  cin.tie(0)->sync_with_stdio(false);
  mvu();
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42