Submission #1009155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009155		makanhulia	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	238 ms	40908 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define freeopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define pb push_back
#define mk make_pair
#define ll long long
#define foor(x,vec) for(auto x:vec ){cout<<x<<" ";}
#define fi first
#define se second
#define MAXN 700069
#define lld long double
#define cha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ffl fflush(stdout)
#define sst string
#define pii pair<ll,ll>
ll mvx[]={0,0,-1,1};
ll mvy[]={1,-1,0,0};


ll dist[4][MAXN];
vector <pii> adj[MAXN];
ll n,m;
void djikstra(ll i,ll x){
    priority_queue<pair<ll,ll> ,vector <pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    REP(j,1,n){
        dist[i][j]=1e18;
    }
      pq.push({0,x});
      dist[i][x]=0;
      while(!pq.empty()){
          ll cost=pq.top().fi;
          ll fr=pq.top().se;
          pq.pop();
          if(cost<=dist[i][fr]){
              for(auto x : adj[fr]){
                  if(dist[i][x.se]>dist[i][fr]+x.fi){
                      dist[i][x.se]=dist[i][fr]+x.fi;
                      pq.push({dist[i][x.se],x.se});
                  }
              }
          }
      }

}

int main(){
    cin>>n>>m;
    ll s,t,u,v;
    cin>>s>>t>>u>>v;
    REP(i,1,m){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({w,v});
        adj[v].pb({w,u});
    }
    djikstra(1,u);
    djikstra(2,t);
    djikstra(3,v);
    ll tot=dist[1][t];
    ll ans=1e18;
    REP(i,1,n){
        if(dist[1][i]+dist[2][i]==tot){
            ans=min({ans,dist[3][i]});
        }
    }
    cout<<ans<<endl;
}

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