Submission #476648

#	Time	Username	Problem	Language	Result	Execution time	Memory
476648		czhang2718	Robot (JOI21_ho_t4)	C++14	100 / 100	1750 ms	107224 KiB

Main

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

typedef pair<int, int> pii;
#define f first
#define s second

template<class T> using pqg=priority_queue<T, vector<T>, greater<T>>;

const int N=100000;
const int M=200000;
int n, m;
map<int, vector<int>> adj[N+1];
int c[M], P[M];
map<pii, pair<int, long long>> dp; //{0/1, min}
map<int, long long> sum[N+1];
pii uv[M];

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for(int i=0; i<m; i++){
    int u, v; cin >> u >> v >> c[i] >> P[i];
    uv[i]={u, v};
    adj[u][c[i]].push_back(i);
    adj[v][c[i]].push_back(i);
    adj[u][0].push_back(i);
    adj[v][0].push_back(i);
    sum[u][c[i]]+=P[i];
    sum[v][c[i]]+=P[i];
    sum[u][0]+=P[i];
    sum[v][0]+=P[i];
  }

  pqg<pair<long long, pii>> pq;
  pq.push({0, {1, 0}});
  while(!pq.empty()){
    pair<long long, pii> p=pq.top(); pq.pop();
    if(dp[p.s].f) continue;
    dp[p.s]={1, p.f};
    int x=p.s.f;
    if(adj[x][p.s.s].empty()) continue;
    for(int e:adj[x][p.s.s]){
      int k=uv[e].f==x?uv[e].s:uv[e].f;
      if(p.s.s){
        if(!dp[{k, 0}].f) pq.push({sum[x][c[e]]-P[e]+p.f, {k, 0}});
      }
      else{
        if(!dp[{k, 0}].f) pq.push({min(sum[x][c[e]]-P[e], (long long)P[e])+p.f, {k, 0}});
        if(!dp[{k, c[e]}].f) pq.push({p.f, {k, c[e]}});
      }
    }
  }

  if(dp[{n, 0}].f) cout <<dp[{n, 0}].s;
  else cout << -1;
}

// when you recolor you're never tied to one color
// star case just works out since you've reached n before hitting the problem
// dp[i][color] - only transition to same color
// dp[i]

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