Submission #626244

#	Time	Username	Problem	Language	Result	Execution time	Memory
626244		Abrar_Al_Samit	Robot (JOI21_ho_t4)	C++17	0 / 100	521 ms	77276 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];
map<int, long long>ans[MX];
map<int, bool>seen[MX];
map<int, vector<int>>colored_edges[MX];
long long minPathCost[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);

    colored_edges[u][c].push_back(i);
    colored_edges[v][c].push_back(i);
  }
 
  priority_queue<tuple<long long, int, int>>pq;
  pq.emplace(0, 1, 0);
  ans[1][0] = 0;
  fill(minPathCost, minPathCost+MX, INF);
 
  while(!pq.empty()) {
    int v = get<1>(pq.top());
    int nerfed = get<2>(pq.top());
    pq.pop();
 
    if(nerfed==0 && !seen[v][nerfed]) {
      minPathCost[v] = min(minPathCost[v], ans[v][nerfed]);
      seen[v][nerfed] = 1;
      for(auto e : g[v]) {
        int to = edge[(edge[0][e]==v)][e];
        long long cur = cost[e] + minPathCost[v];

        if(!ans[to].count(e)) ans[to][e] = INF;
        if(ans[to][e]>cur) {
          ans[to][e] = cur;
          pq.emplace(cost[e]-cur, to, e);
        }
        cur = sum[v][color[e]] - cost[e] + minPathCost[v];

        if(!ans[to].count(0)) ans[to][0] = INF;
        if(ans[to][0]>cur) {
          ans[to][0] = cur;
          pq.emplace(-cur, to, 0);
        }
      }
    } else if(seen[v][color[nerfed]]==0) {
      seen[v][color[nerfed]] = 1;
      minPathCost[v] = min(minPathCost[v], ans[v][nerfed]);

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

        if(!ans[to].count(0)) ans[to][0] = INF;
        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(best, b.second);
  }
  if(best==INF) best = -1;
  cout<<best<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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