RUPC2018 day1 E: いたずらされたグラフ

問題ページ
Aizu Online Judge Arena

解法

a,b,c の3頂点で閉路となっていてこのような閉路がN個ある。閉路の3辺から1つの辺を選んで構成したグラフでのs-t間の最短経路を求めたい。
経路a->bよりも経路a->c、c->bとたどっていくような経路の方が短くなることはありえない。したがって、辺を選ぶのを無視して有り得る辺を全て張ったグラフでの最短経路を考えたとき、閉路の3辺のうち2辺以上を使うような経路になることはありえない。
つまり辺を6M本張ったようなグラフを構築しdijkstraなどでs-t間の最短経路を求めればよい。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

vector<PII> g[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m, s, t;
  cin >> n >> m >> s >> t;
  s--, t--;
  REP(i, m) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--, b--, c--;
    g[a].PB({b, d});
    g[b].PB({a, d});
    g[a].PB({c, d});
    g[c].PB({a, d});
    g[b].PB({c, d});
    g[c].PB({b, d});
  }

  VI d(n);
  auto dijkstra = [&](int s) {
    d.assign(n, LLINF);
    d[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push(PII{d[s], s});

    while(que.size()) {
      PII p = que.top(); que.pop();
      int v = p.second;
      if(d[v] < p.first) continue;
      for(PII &e: g[v]) {
        if(d[e.first] > d[v] + e.second) {
          d[e.first] = d[v] + e.second;
          que.push(PII{d[e.first], e.first});
        }
      }
    }
  };
  dijkstra(s);
  cout << d[t] << endl;

  return 0;
}