Submission #1218844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218844		escobrand	Robot (JOI21_ho_t4)	C++20	100 / 100	2209 ms	79504 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long 
#define fi first
#define se second
int t,n,i,u,v,c,m;
ll w;
const int maxn = 1e5 + 10;
const ll inf = 1e16;
struct edge
{
  int to,c;
  ll w;
  bool operator < (const edge &b)const
  {
    if(w != b.w)return w > b.w;
    return to > b.to;
  }
};
map<int,vector<edge>>adj[maxn];
map<int,ll> sum[maxn];
ll d[maxn];
map<int,ll> pass[maxn];

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    while(m--)
    {
      cin>>u>>v>>c>>w;
      adj[u][c].eb({v,c,w});
      adj[v][c].eb({u,c,w});
      sum[u][c] += w;
      sum[v][c] += w;
    }
    priority_queue<edge>q;
    q.push({1,0,0});
    for(i = 2;i<=n;i++)d[i] = inf;
    while(q.size())
    {
      i = q.top().to;
      w = q.top().w;
      c = q.top().c;
      q.pop();
      if(c)
      {
        if(pass[i][c] != w)continue;
        for(auto k : adj[i][c])
        {
          ll tmp = sum[i][c] - k.w;
          if(d[k.to] > tmp + w )
          {
            d[k.to] = tmp + w;
            q.push({k.to,0,d[k.to]});
          }
        }
      }
      else
      {
        if(d[i] != w)continue;
        for(auto j : adj[i])
        {
          for(auto k : j.se)
          {
            ll tmp = sum[i][k.c] - k.w;
            if(d[k.to] > tmp + w)
            {
              d[k.to] = tmp + w;
              q.push({k.to,0,d[k.to]});
            }
            
            if(d[k.to] > k.w + w)
            {
              d[k.to] = k.w + w;
              q.push({k.to,0,d[k.to]});
            }
            
            if(pass[k.to].find(k.c) == pass[k.to].end() || pass[k.to][k.c] > w)
            {
              pass[k.to][k.c] = w;
              q.push({k.to,k.c,w});
            }
          }
        }
      }
    }
    
    if(d[n] >= inf)d[n] =-1;
    cout<<d[n];
    
    return 0;
}

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