Submission #380373

#	Time	Username	Problem	Language	Result	Execution time	Memory
380373		loctildore	Robot (JOI21_ho_t4)	C++14	0 / 100	629 ms	50116 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
#define endl '\n'
#define all(x) begin(x), end(x)
ll n,m;
ll a,b,c,p;
struct edge{
  ll target,c,p;
};
vector<edge> grph[100069];
set<ll> grphcol[100069];
set<ll> dupcol[100069];
bool done[100069];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>m;
  for (ll i = 0; i < m; i++) {
    cin>>a>>b>>c>>p;
    a--;b--;
    grph[a].push_back({b,c,p});
    grph[b].push_back({a,c,p});
    if (grphcol[a].find(c)!=grphcol[a].end()) {
      if (dupcol[a].find(c)==dupcol[a].end()) {
        dupcol[a].insert(c);
      }
    }
    else{
      grphcol[a].insert(c);
    }
    if (grphcol[b].find(c)!=grphcol[b].end()) {
      if (dupcol[b].find(c)==dupcol[b].end()) {
        dupcol[b].insert(c);
      }
    }
    else{
      grphcol[b].insert(c);
    }
  }
  pq.push({0,0});
  while (pq.size()) {
    auto temp=pq.top();
    pq.pop();
    if (done[temp.s]) {
      continue;
    }
    done[temp.s]=true;
    if (temp.s==n-1) {
      cout<<temp.f<<endl;
      return 0;
    }
    for (auto i:grph[temp.s]) {
      if (dupcol[temp.s].find(i.c)==dupcol[temp.s].end()) {
        pq.push({temp.f,i.target});
      }
      else{
        pq.push({temp.f+i.p,i.target});
      }
    }
  }
  cout<<"-1"<<endl;
  return 0;
}

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