Submission #526157

#	Time	Username	Problem	Language	Result	Execution time	Memory
526157		vijay	Robot (JOI21_ho_t4)	C++17	24 / 100	887 ms	82612 KiB

Main

#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <climits>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <bitset>
#include <numeric>
#include <cstring>
using namespace std;

const int MAXN = 2e5 + 5;
const int LOGN = 18; // log of MAXN base 2
const int INF = 1e18;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;

#define trav(a, x) for (auto& a: x)
#define all(x) begin(x), end(x)
#define mp make_pair
#define pb push_back
#define f first
#define s second

struct Edge {
  int to, color;
  ll cost;
};

int main(){

  cin.tie(0)->sync_with_stdio(0);

  // ifstream cin;
  // cin.open("test.in");

  int N, M; cin >> N >> M;
  map<int, ll> dp2[100001], sum[100001];
  map<int, vector<Edge> > graph[100001];
  ll dp[100001];
  for(int i = 0; i < M; i++){
    int a, b, col; ll cost;
    cin >> a >> b >> col >> cost;
    graph[a][col].pb({b, col, cost});
    graph[b][col].pb({a, col, cost});
    sum[a][col] += cost;
    sum[b][col] += cost;
  }

  memset(dp, 0x3f, sizeof(dp));
  dp[1] = 0;
  priority_queue<tuple<ll, int, int> > pq;
  pq.push({0, 1, 0});
  while(!pq.empty()){
    ll cost; int node, col;
    tie(cost, node, col) = pq.top();
    pq.pop();

    cost = -cost;

    if(col > 0){
      if(dp2[node][col] != cost){
        continue;
      }
      for(Edge i: graph[node][col]){
        ll case1 = sum[node][col] - i.cost + cost;
        if(case1 < dp[i.to]){
          dp[i.to] = case1;
          pq.push({-dp[i.to], i.to, 0});
        }
      }
    } else {
      if(dp[node] != cost){
        continue;
      }

      for(auto& i: graph[node]){
        for(Edge j: i.second){
          ll case1 = sum[node][j.color] - j.cost + cost;
          if(case1 < dp[j.to]){
            dp[j.to] = case1;
            pq.push({-dp[j.to], j.to, 0});
          }

          case1 = j.cost + cost;
          if(case1 < dp[j.to]){
            dp[j.to] = case1;
            pq.push({-dp[j.to], j.to, 0});
          }

          case1 = cost;
          if(!dp2[j.to].count(j.color) || case1 < dp2[j.to][j.color]){
            dp2[j.to][j.color] = case1;
            pq.push({-dp2[j.to][j.color], j.to, j.color});
          }
        }
      }
    }
  }

  cout << (dp[N] > INF ? -1 : dp[N]) << "\n";
  return 0;
}

Compilation message (stderr)

Main.cpp:22:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int INF = 1e18;
      |                 ^~~~

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