제출 #625806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625806		Abrar_Al_Samit	Robot (JOI21_ho_t4)	C++17	34 / 100	3062 ms	67336 KiB

Main

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

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

vector<int>g[MX];
long long cost[MX], color[MX];
int edge[2][MX];
map<int,long long>sum[MX];
void PlayGround() {
  int n, m;
  cin>>n>>m;

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

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

    g[u].push_back(i);
    g[v].push_back(i);
  }
  for(int i=1; i<=n; ++i) {
    sort(g[i].begin(), g[i].end());
  }

  vector<vector<long long>>ans(n+1, vector<long long>(1, INF));
  vector<vector<bool>>vis(n+1, vector<bool>(1, false));

  for(int i=1; i<=m; ++i) {
    ans[edge[0][i]].push_back(INF);
    ans[edge[1][i]].push_back(INF);

    vis[edge[0][i]].push_back(false);
    vis[edge[1][i]].push_back(false);
  }

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

  while(!pq.empty()) {
    int v = get<1>(pq.top());
    int id = get<2>(pq.top());
    int nerfed = -1;
    if(id) nerfed = g[v][id-1];

    pq.pop();
    if(vis[v][id]) continue;
    vis[v][id] = 1;

    for(auto e : g[v]) {
      int to = edge[(edge[0][e]==v)][e];
      long long cur = cost[e] + ans[v][id];

      int nextID = lower_bound(g[to].begin(), g[to].end(), e) - g[to].begin()+1;

      if(ans[to][nextID]>cur) {
        ans[to][nextID] = cur;
        pq.emplace(-cur, to, nextID);
      }
      cur = sum[v][color[e]] - cost[e] + ans[v][id];
      if(nerfed!=-1 && color[nerfed]==color[e]) cur -= cost[nerfed];
      if(ans[to][0]>cur) {
        ans[to][0] = cur;
        pq.emplace(-cur, to, 0);
      }
    }
  }



  long long best = INF;
  for(auto b : ans[n]) {
    best = min(b, best);
  }
  if(best==INF) best = -1;
  cout<<best<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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