제출 #1008949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008949		makanhulia	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	309 ms	23900 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define fi first
#define se second
#define nikah ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll maxn = 1e5+7;

ll n,m,s,t,u,v;
vector<pll>adj[maxn];
priority_queue<pll>pq;
set<pll>bt;

void sp1 () {
  vector<pll>dist(n+2 ,{1e18, 0});
  dist[s].fi = 0;
  pq.push({0, s});
  
  while (!pq.empty()) {
    auto p = pq.top(); pq.pop();
    ll cost = -p.fi, now = p.se;
    
    if (dist[now].fi < cost) continue;
    
    for (auto x : adj[now]) {
      ll weight = x.fi, nextnode = x.se;
      if (dist[nextnode].fi > cost + weight) {
        dist[nextnode].fi = cost + weight;
        dist[nextnode].se = now;
        pq.push({-dist[nextnode].fi, nextnode});
      }
    }
  }
  ll cur = t;
  while (dist[cur].se != s) {
    bt.insert({cur, dist[cur].se});
    bt.insert({dist[cur].se, cur});
    cur = dist[cur].se;
  }
  bt.insert({cur, dist[cur].se});
  bt.insert({dist[cur].se, cur});
}

ll sp2 () {
  vector<ll>dist(n+2, 1e18);
  dist[u] = 0;
  pq.push({0, u});
  
  while (!pq.empty()) {
    auto p = pq.top(); pq.pop();
    ll cost = -p.fi, now = p.se;
    
    if (dist[now] < cost) continue;
    
    for (auto x : adj[now]) {
      ll weight = x.fi, nextnode = x.se;
      if (bt.count({nextnode, now})) weight = 0;
      if (dist[nextnode] > cost + weight) {
        dist[nextnode] = cost + weight;
        pq.push({-dist[nextnode], nextnode});
      }
    }
  }
  /*for (ll i=1; i<=n; i++) {
    cout<<i<<" : "<<dist[i]<<endl;
  }*/
  return dist[v];
}

int main () {
  nikah
  cin>>n>>m>>s>>t>>u>>v;
  for (ll i=1; i<=m; i++) {
    ll a,b,c; cin>>a>>b>>c;
    adj[a].pb({c,b});
    adj[b].pb({c,a});
  }
  sp1();
  /*for (auto p : bt) {
    cout<<p.fi<<" "<<p.se<<endl;
  }*/
  cout<<sp2()<<endl;
}

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