Submission #1125156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125156		barkolorious	Robot (JOI21_ho_t4)	C++20	100 / 100	975 ms	82704 KiB

Main

// barkolorious - 08 December 2024
// in god, do we trust? 
#include <bits/stdc++.h>
using namespace std;

#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define all(v) (v).begin(), (v).end()
#define int long long
#define pb  push_back
#define sz  size
#define fr  first
#define sc  second
#define __  << " " << 

const int N = 1e5 + 1;

struct Edge {
  int to, color, price;
};

map<int, vector<Edge>> adj[N];
int dp[N];
map<int, int> dp2[N], price_sum[N];

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

  for (int i = 0; i < m; i++) {
    int u, v, c, p; cin >> u >> v >> c >> p;
    adj[u][c].pb({v, c, p});
    adj[v][c].pb({u, c, p});
    price_sum[u][c] += p;
    price_sum[v][c] += p;
  }

  fill(dp, dp + N, 1e15);
  priority_queue<tuple<int, int, int>> pq; // dist, node, last color

  pq.push({0, 1, 0});
  dp[1] = 0;
  
  while (!pq.empty()) {
    int node, dist, color;
    tie(dist, node, color) = pq.top();
    pq.pop();
    dist = -dist;    

    if (color) {
      if (dp2[node][color] != dist) continue;
      for (Edge edge : adj[node][color]) {
        int case1 = dist + (price_sum[node][color] - edge.price);
        if (case1 < dp[edge.to]) {
          dp[edge.to] = case1;
          pq.push({-dp[edge.to], edge.to, 0});
        }
      }
    } else {
      if (dp[node] != dist) continue;
      for (auto colored_edges : adj[node]) {
        for (auto edge : colored_edges.sc) {
          int case1 = dist + (price_sum[node][edge.color] - edge.price);
          if (case1 < dp[edge.to]) {
            dp[edge.to] = case1;
            pq.push({-dp[edge.to], edge.to, 0});
          }

          int case2 = dist + edge.price;
          if (case2 < dp[edge.to]) {
            dp[edge.to] = case2;
            pq.push({-dp[edge.to], edge.to, 0});
          }

          int case3 = dist;
          if (!dp2[edge.to].count(edge.color) || case3 < dp2[edge.to][edge.color]) {
            dp2[edge.to][edge.color] = case3;
            pq.push({-dp2[edge.to][edge.color], edge.to, edge.color});
          }
        }
      }
    }
  }

  cout << ((dp[n] == 1e15) ? -1 : dp[n]) << endl;
}

/*
-- Sample 1 --
Input:
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2
Output:
3

-- Sample 2 --
Input:
5 2
1 4 1 2
3 5 1 4
Output:
-1

-- Sample 3 --
Input:
5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1
Output:
1

-- Sample 4 --
Input:
13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20
Output:
7
*/

/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\Olympiads\JOI21\JOI21_ho_t4.cpp" -o _run
*/

int32_t main () {
  #ifndef LOCAL
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
  #endif

  #ifdef LOCAL
    clock_t __START__ = clock();
    FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
    FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
  #endif

  solve();

  #ifdef LOCAL
    fclose(__FILE_IN__);
    fclose(__FILE_OUT__);
    cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
  #endif

  return 0;
}

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