Submission #1092176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092176		vu28082007	Robot (JOI21_ho_t4)	C++14	100 / 100	221 ms	30964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
#define ll long long
#define pb push_back
ll n, m, dist[N], dem[N], save[N], sum[N],a ,b ,c, p;
vector<array<ll,3>> adj[N];
priority_queue<array<ll,2>, vector<array<ll,2>>, greater<array<ll,2>> > pq;
bool vs[N];
int main() 
{
    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++)
    {
      dist[i]=1e18;
      vs[i]=0;
    }
    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(e[2], sum[e[1]] - e[2]))
          {
            dist[e[0]]=dist[k[1]] + min(e[2], sum[e[1]] - 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];
    return 0;
}

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