제출 #1008941

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

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define fi first
#define sec second

const ll MOD = 998244353;
const ll N = 2e5 + 5;
const ll INF = 1e18;

vector<pii>adj[N];
ll dist[N], dist2[N];

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
  int tc = 1;
  // cin >> tc;
  while(tc--){
    ll n,m; cin >> n >> m;
    ll s,t; cin >> s >> t;
    ll u,v; cin >> u >> v;
    map<pii,ll>path;
    for(int i=1;i<=m;i++){
      ll a,b,w; cin >> a >> b >> w;
      adj[a].pb({b,w});
      adj[b].pb({a,w});
      path[{a,b}] = path[{b,a}] = w;
    }
    for(int i=1;i<=n;i++) dist[i] = dist2[i] = INF;
    dist[s] = 0;
    set<pii>st;
    st.insert({dist[s], s});
    while(!st.empty()){
      auto x = *st.begin(); st.erase(x);
      if(dist[x.sec] != x.fi) continue;
      for(auto i : adj[x.sec]){
        if(dist[i.fi] > dist[x.sec] + i.sec){
          dist[i.fi] = dist[x.sec] + i.sec;
          st.insert({dist[i.fi], i.fi});
        }
      }
    }
    ll cur = t;
    while(cur != s){
      for(auto i : adj[cur]){
        if(dist[i.fi] == dist[cur] - i.sec){
          path[{cur,i.fi}] = path[{i.fi,cur}] = 0;
          cur = i.fi;
          break;
        }
      }
    }
    dist2[u] = 0;
    st.insert({dist2[u], u});
    while(!st.empty()){
      auto x = *st.begin(); st.erase(x);
      for(auto i : adj[x.sec]){
        if(dist2[i.fi] > dist2[x.sec] + min(path[{i.fi, x.sec}], i.sec)){
          dist2[i.fi] = dist2[x.sec] + min(path[{i.fi, x.sec}], i.sec);
          st.insert({dist2[i.fi], i.fi});
        }
      }
    }
    cout << dist2[v] << "\n";
  }
}
/*

*/

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