Submission #434849

#	Time	Username	Problem	Language	Result	Execution time	Memory
434849		chirathnirodha	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	605 ms	22828 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,dpt;
vector<ll> su,sv,tu,tv;
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 bfs(){
	queue<int> q;
	q.P(t);
	tu[t]=dpu[t];tv[t]=dpv[t];
	while(!q.empty()){
		int c=q.front();q.pop();
		for(int i=0;i<adj[c].size();i++){
			ll x=adj[c][i].F,y=adj[c][i].S;
			if(dps[x]+y!=dps[c])continue;
			if(tu[x]>tu[c] || tv[x]>tv[c] || tu[x]>dpu[x] || tv[x]>dpv[x])q.P(x);
			tu[x]=min(tu[x],min(tu[c],dpu[x]));
			tv[x]=min(tv[x],min(tv[c],dpv[x]));
		}
	}
	q.P(s);
	su[s]=dpu[s];sv[s]=dpv[s];
	while(!q.empty()){
		int c=q.front();q.pop();
		for(int i=0;i<adj[c].size();i++){
			ll x=adj[c][i].F,y=adj[c][i].S;
			if(dpt[x]+y!=dpt[c])continue;
			if(su[x]>su[c] || sv[x]>sv[c] || su[x]>dpu[x] || sv[x]>dpv[x])q.P(x);
			su[x]=min(su[x],min(su[c],dpu[x]));
			sv[x]=min(sv[x],min(sv[c],dpv[x]));
		}
	}
}
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);
	dpt=dijkstra(t);
	dpu=dijkstra(u);
	dpv=dijkstra(v);
	ans=dpu[v];
	for(int i=0;i<n;i++){
		su.PB(INT64_MAX/2);
		sv.PB(INT64_MAX/2);
		tu.PB(INT64_MAX/2);
		tv.PB(INT64_MAX/2);
	}
	bfs();
	for(int i=0;i<n;i++){
		ans=min(ans,su[i]+tv[i]);
		ans=min(ans,sv[i]+tu[i]);
	}
	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 bfs()':
commuter_pass.cpp:49: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]
   49 |   for(int i=0;i<adj[c].size();i++){
      |               ~^~~~~~~~~~~~~~
commuter_pass.cpp:61: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]
   61 |   for(int i=0;i<adj[c].size();i++){
      |               ~^~~~~~~~~~~~~~

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