Submission #626421

#	Time	Username	Problem	Language	Result	Execution time	Memory
626421		Abrar_Al_Samit	Robot (JOI21_ho_t4)	C++17	100 / 100	1259 ms	90644 KiB

Main

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int MX = 2e5 + 5;
const long long INF = 1e18;

vector<int>g[MX/2];
int cost[MX], color[MX];
int edge[2][MX];
map<int,vector<int>>colored_edges[MX/2];
map<int, long long>ans[MX/2], sum[MX/2];

void PlayGround() {
  int n, m;
  cin>>n>>m;

  for(int i=1, u,v,p,c; i<=m; ++i) {
    cin>>u>>v>>c>>p;
    g[u].push_back(i);
    g[v].push_back(i);
    color[i] = c, cost[i] = p;
    edge[0][i] = u, edge[1][i] = v;

    colored_edges[u][c].push_back(i);
    colored_edges[v][c].push_back(i);

    sum[v][c] += p;
    sum[u][c] += p;
  }


  priority_queue<tuple<long long, int, int>>pq;
  pq.emplace(0, 1, 0);
  ans[1][0] = 0;


  while(!pq.empty()) {
    int v, nerfed;
    long long c;
    tie(c, v, nerfed) = pq.top();
    pq.pop();

    if(ans[v][nerfed]!=-c) continue;

    if(nerfed) {
      for(auto e : colored_edges[v][nerfed]) {
        int to = edge[(edge[0][e]==v)][e];
        long long cur = ans[v][nerfed] + sum[v][nerfed] - cost[e];

        if(!ans[to].count(0) || ans[to][0]>cur) {
          ans[to][0] = cur;
          pq.emplace(-cur, to, 0);
        }
      }
    } else {
      for(auto e : g[v]) {
        int to = edge[(edge[0][e]==v)][e];
        long long cur = ans[v][nerfed] + sum[v][color[e]] - cost[e];

        if(!ans[to].count(0) || ans[to][0]>cur) {
          ans[to][0] = cur;
          pq.emplace(-cur, to, 0);
        }

        cur = ans[v][nerfed];
        if(!ans[to].count(color[e]) || ans[to][color[e]]>cur) {
          ans[to][color[e]] = cur;
          pq.emplace(-cur, to, color[e]);
        }

        cur = ans[v][nerfed] + cost[e];
        if(!ans[to].count(0) || ans[to][0]>cur) {
          ans[to][0] = cur;
          pq.emplace(-cur, to, 0);
        }
      }
    }
  }

  if(ans[n].count(0)==0) ans[n][0] = INF;
  long long best = ans[n][0];

  if(best==INF) best = -1;
  cout<<best<<'\n';
}
int main() {
  ios_base::sync_with_stdio();
  cin.tie(nullptr);

  PlayGround();
  return 0;
}

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