ありよりのあり

\主に競プロ備忘録/

ARC 061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題概要

N頂点M辺のグラフが与えられる.各辺には種類c_iがある.
頂点1からNに行くには最低何種類のパスをまたぐ必要があるか.
* 種類1 -> 2 -> 1 は3種類と数える.
2<=N<=105, 0<=M<=2*106, 1 <= c_i <= 106

解法

a b cのような辺に対して,
(a,c) <=> (a,0)
↕︎
(b,c) <=> (b,0)
と辺を張って最終的な答えを2で割るとうまくいく.(<=>はコスト1,↕︎はコスト0)
片方だけ1にして最終的な出力にしても良い.
ただし,全ての状態数NxMについて領域を確保するとMLEするのでunordered_mapを使って上手いことやる.
unordered_mapとmapの違いは前者がhashでO(1), 後者が二分木でO(logN).
(頂点,会社)を頂点としても良いが,64ビット変数に押し込むと楽.
追加する頂点数は高々辺の数*2なので,O*1で解ける.

解説放送の方法は(a,c)と(b,c)を同一視して,同じ会社の他社を介さずに行ける頂点全てに辺を張って2部グラフを作っていた.
こっちの方がノードが少なくなるので多分高速.

メモ

典型ぽいので覚えよう.
PlをPと書いてオーバーフローするクソみたいなミスした.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;
const int MAX_N = 100005;

class Edge{
  public:
    int cost; ll to;
    Edge(int cost,ll to)
      :cost(cost),to(to){}
};

void dijkstra(ll start,unordered_map<ll,vector<Edge>> &graph,unordered_map<ll,int> &dist){
  priority_queue<Pl,vector<Pl>,greater<Pl>> que;
  dist[start] = 0;
  que.push(Pl(0,start));
  while(!que.empty()){
    Pl p=que.top(); que.pop();
    ll v=p.second; //行き先
    if(dist[v]==0&&v!=0LL) dist[v] = INF;
    if(dist[v]<p.first) continue;
    for(Edge e: graph[v]){
      if(dist[e.to]==0&&e.to!=0LL) dist[e.to] = INF;
      if(dist[v]+e.cost<dist[e.to]){
        dist[e.to]=dist[v]+e.cost;
        que.push(Pl(dist[e.to],e.to));
      }
    }
  }
  return ;
}

void add_edge(ll p,ll q,ll c,unordered_map<ll,vector<Edge>> &graph){
  ll p0,pc,q0,qc;
  p0 = ll(p); q0 = ll(q);
  pc = p0 | (c<<30);
  qc = q0 | (c<<30);
  graph[p0].pb(Edge(1,pc));
  graph[pc].pb(Edge(1,p0));
  graph[pc].pb(Edge(0,qc));
  graph[qc].pb(Edge(0,pc));
  graph[qc].pb(Edge(1,q0));
  graph[q0].pb(Edge(1,qc));
}

int main(){
  ll N,M; cin >> N >> M;
  unordered_map<ll,vector<Edge>> graph;
  unordered_map<ll,int> dist;
  rep(i,M){
    ll p,q,c; scanf("%lld%lld%lld",&p,&q,&c);
    p--; q--;
    add_edge(p,q,c,graph);
  }
  dijkstra(0LL,graph,dist);
  ll ans;
  if(dist[ll(N-1)]!=0 && dist[ll(N-1)]!=INF){
    ans = dist[ll(N-1)]/2LL;
  }else{
    ans = -1LL;
  }
  cout << ans << endl;
  return 0;
}

*1:N+M)log(N+M