제출 #1167642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167642		afvrevebva	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	1136 ms	16024 KiB

commuter_pass

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

const ll C=1e9;
const ll M=2e5;

vector<vector<pair<int,ll>>> adj;

void f(vector<ll> &v,int x){
    v[x]=0;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        for(pair<int,ll> p:adj[i]){
            ll j,c;
            tie(j,c)=p;
            if(v[j]>v[i]+c){
                v[j]=v[i]+c;
                q.push(j);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,m,s,t,u,v;
    cin>>n>>m>>s>>t>>u>>v;
    adj=vector<vector<pair<int,ll>>>(n+1);
    for(int i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    vector<ll> dv(n+1,C*M);
    vector<ll> dt(n+1,C*M);
    vector<ll> ds(n+1,C*M);
    f(dv,v);
    f(ds,s);
    f(dt,t);
    ll tot=C*M;
    for(int i=1;i<=n;i++){
        tot=min(tot,ds[i]+dt[i]);
    }
    ll res=dv[s];
    for(int i=1;i<=n;i++){  
        if(ds[i]+dt[i]==tot){
            res=min(res,dv[i]);
        }
    }
    cout<<res;
}

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