Submission #434759

#	Time	Username	Problem	Language	Result	Execution time	Memory
434759		chirathnirodha	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2096 ms	21472 KiB

commuter_pass

//Coded by Chirath Nirodha
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
#define ER erase
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
int n,m,s,t,u,v;
vector<pair<ll,ll> > adj[100000];
vector<ll> dps,dpu,dpv;
ll minu,minv;
vector<ll> dijkstra(int a){
	vector<ll> dp;
	for(int i=0;i<n;i++)dp.PB(INT64_MAX);
	dp[a]=0;
	priority_queue<pair<ll,ll> > q;
	q.P(MP(0,a));
	while(!q.empty()){
		pair<ll,ll> c=q.top();q.pop();
		for(int i=0;i<adj[c.S].size();i++){
			ll x=adj[c.S][i].F,y=adj[c.S][i].S;
			if(dp[x]>dp[c.S]+y){
				dp[x]=dp[c.S]+y;
				q.P(MP(-dp[x],x));
			}
		}
	}
	return dp;
}
ll ans;
void dfs(int x,ll minu,ll minv){
	if(x==s){
		ans=min(ans,minu+minv);
		return;
	}
	for(int i=0;i<adj[x].size();i++){
		ll a=adj[x][i].F,b=adj[x][i].S;
		if(dps[x]==dps[a]+b){
			dfs(a,min(minu,dpu[a]),min(minv,dpv[a]));
		}
	}
}
void solve(){
    cin>>n>>m>>s>>t>>u>>v;
	s--;t--;u--;v--;
	for(int i=0;i<m;i++){
		ll x,y,z;cin>>x>>y>>z;x--;y--;
		adj[x].PB(MP(y,z));adj[y].PB(MP(x,z));
	}
	dps=dijkstra(s);
	dpu=dijkstra(u);
	dpv=dijkstra(v);
	ans=dpu[v];
	dfs(t,dpu[t],dpv[t]);
	cout<<ans<<endl;
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int)':
commuter_pass.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0;i<adj[c.S].size();i++){
      |               ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(int, ll, ll)':
commuter_pass.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<adj[x].size();i++){
      |              ~^~~~~~~~~~~~~~

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