제출 #167422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167422		cbertram	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	435 ms	26960 KiB

commuter_pass

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

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<string> vs;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i = a; i < b; i++)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int N, M;
  cin >> N;
  cin >> M;
  int S, T;
  cin >> S;
  cin >> T;
  S--;
  T--;
  int U, V;
  cin >> U;
  cin >> V;
  U--;
  V--;

  vvpll conn(N, vpll(0));
  rep(m,0,M) {
    long a, b, c;
    cin >> a;
    cin >> b;
    cin >> c;
    a--;
    b--;
    conn[a].push_back(make_pair(b, c));
    conn[b].push_back(make_pair(a, c));
  }

  vll distU(N);
  vb vis(N);
  priority_queue<pll, vpll, greater<pll>> pq1;
  pq1.push(make_pair(0,U));
  while(!pq1.empty()) {
    ll n = pq1.top().second;
    ll d = pq1.top().first;
    pq1.pop();
    if(vis[n]) continue;
    vis[n] = true;
    distU[n] = d;
    rep(i,0,(int)conn[n].size())
      if(!vis[conn[n][i].first])
	pq1.push(make_pair(d+conn[n][i].second, conn[n][i].first));
  }
  vll distV(N);
  fill(all(vis), false);
  pq1.push(make_pair(0,V));
  while(!pq1.empty()) {
    ll n = pq1.top().second;
    ll d = pq1.top().first;
    pq1.pop();
    if(vis[n]) continue;
    vis[n] = true;
    distV[n] = d;
    rep(i,0,(int)conn[n].size())
      if(!vis[conn[n][i].first])
	pq1.push(make_pair(d+conn[n][i].second, conn[n][i].first));
  }
  //rep(n,0,N) cerr << distV[n] << ' ';
  //cerr << '\n';

  fill(all(vis), false);
  priority_queue<pair<pair<ll,pair<ll,pair<ll,ll>>>,ll>,
		 vector<pair<pair<ll,pair<ll,pair<ll,ll>>>,ll>>,
		 greater<pair<pair<ll,pair<ll,pair<ll,ll>>>,ll>>> pq;
  pq.push(make_pair(make_pair(0,make_pair(distU[S]+distV[S],make_pair(distU[S],distV[S]))),S));
  while(!pq.empty()) {
    ll dS = pq.top().first.first;
    ll dUV = pq.top().first.second.first;
    ll dU = pq.top().first.second.second.first;
    ll dV = pq.top().first.second.second.second;
    ll n = pq.top().second;
    pq.pop();
    //cerr << "n?: " << n << '\n';
    if(vis[n]) continue;
    vis[n] = true;
    //cerr << "n: " << n << '\n';
    if(n == T) {
      //cout << dUV << ", " << dU << ", " << dV << ", " << dS << '\n';
      cout << min(distU[V], dUV) << '\n';
      break;
    }
    rep(i,0,(int)conn[n].size())
      if(!vis[conn[n][i].first]) {
	ll nn = conn[n][i].first;
	ll ndS = dS+conn[n][i].second;
	ll ndU = min(dU, distU[nn]);
	ll ndV = min(dV, distV[nn]);
	ll ndUV = ndU+ndV;
	pq.push(make_pair(make_pair(ndS,make_pair(ndUV,make_pair(ndU,ndV))),nn));
      }
  }
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45