Submission #434764

#	Time	Username	Problem	Language	Result	Execution time	Memory
434764		chirathnirodha	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	315 ms	20240 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 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];
	ll minuv[n][2];
	for(int i=0;i<n;i++){
		minuv[i][0]=dpu[i];
		minuv[i][1]=dpv[i];
	}
	queue<ll> q;q.P(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((minuv[x][0]>minuv[c][0]) || (minuv[x][1]>minuv[c][1]))q.P(x);
			minuv[x][0]=min(minuv[x][0],minuv[c][0]);
			minuv[x][1]=min(minuv[x][1],minuv[c][1]);
		}
	}
	ans=min(ans,minuv[s][0]+minuv[s][1]);
	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 solve()':
commuter_pass.cpp:65: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]
   65 |   for(int i=0;i<adj[c].size();i++){
      |               ~^~~~~~~~~~~~~~

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