Submission #1099513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099513		akamizane	Robot (JOI21_ho_t4)	C++17	100 / 100	791 ms	87812 KiB

Main

#include<bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using pii = pair<int,long long>;
 
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll mod = 1e9 + 7;

const int maxn = 1e5 + 5;

void solve(){
  int n, m;
  cin >> n >> m;
  map<int, vector<array<long long,3>>> graph[n + 1];
  map<int, ll> psum[n + 1];
  map<int, ll> dp2[n + 1];
  vector<ll> dp(n + 1, 1e18);
  REP(i, m){
    int u, v, c;
    ll p;
    cin >> u >> v >> c >> p;
    graph[u][c].pb({v, c, p});
    graph[v][c].pb({u, c, p});
    psum[u][c] += p;
    psum[v][c] += p;
  }
  using T = array<long long, 3>;
  priority_queue<T, vector<T>, greater<T>> pq;
  pq.push({0, 1, 0});
  dp[1] = 0;
  while(pq.size()){
    auto [val, u, cur] = pq.top();
    pq.pop();
    if (cur){
      if (dp2[u][cur] != val) continue;
      for (auto [to, c, p] : graph[u][cur]){
        ll case1 = psum[u][c] - p;
        if (val + case1 < dp[to]){
          dp[to] = val + case1;
          pq.push({dp[to], to, 0});
        }
      }
    }
    else{
      if (dp[u] != val) continue;
      for (auto color : graph[u]){
        for (auto [to, c, p] : color.se){
          ll case1 = psum[u][c] - p + val;
          if (case1 < dp[to]){
            dp[to] = case1;
            pq.push({case1, to, 0});
          }
          ll case2 = p + val;
          if (case2 < dp[to]){
            dp[to] = case2;
            pq.push({case2, to, 0});
          }
          ll case3 = val;
          if (!dp2[to].count(c) || case3 < dp2[to][c]){
            dp2[to][c] = case3;
            pq.push({case3, to, c});
          }
        }
      }
    }
  }
  cout << (dp[n] == 1e18 ? -1 : dp[n]);
}
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    cerr << "- Case #" << _ << ": \n";
    solve();
    el;
  }
  return 0;
}

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