Submission #434688

#	Time	Username	Problem	Language	Result	Execution time	Memory
434688		chirathnirodha	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2091 ms	19792 KiB

commuter_pass

//Coded by Chirath Nirodha
#include<bits/stdc++.h>
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;
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;
multiset<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){
	if(x==0){
		ans=min(ans,*minu.begin()+*minv.begin());
		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){
			minv.I(dpv[a]);
			minu.I(dpu[a]);
			dfs(a);
			minu.ER(minu.find(dpu[a]));
			minv.ER(minv.find(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];
	minu.I(dpu[t]);
	minv.I(dpv[t]);
	dfs(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:32: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]
   32 |   for(int i=0;i<adj[c.S].size();i++){
      |               ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:48: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]
   48 |  for(int i=0;i<adj[x].size();i++){
      |              ~^~~~~~~~~~~~~~

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