Submission #127313

#	Time	Username	Problem	Language	Result	Execution time	Memory
127313		HungAnhGoldIBO2020	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	421 ms	23180 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=1e5+2;
const int inf=1e18+2;
priority_queue<pair<int,int> > lis;
vector<pair<int,int> > adj[N];
int dis[N],dis1[N],ans,min1[N],dis2[N],min2[N],dis3[N];
void dijkstra(int x){
	for(int i=0;i<adj[x].size();i++){
		if(dis[adj[x][i].first]>dis[x]+adj[x][i].second){
			dis[adj[x][i].first]=dis[x]+adj[x][i].second;
			lis.push({-dis[adj[x][i].first],adj[x][i].first});
		}
	}
}
void dijkstra1(int x){
	for(int i=0;i<adj[x].size();i++){
		if(dis1[adj[x][i].first]>dis1[x]+adj[x][i].second){
			dis1[adj[x][i].first]=dis1[x]+adj[x][i].second;
			lis.push({-dis1[adj[x][i].first],adj[x][i].first});
		}
	}
}
void dijkstra3(int x){
	for(int i=0;i<adj[x].size();i++){
		if(dis3[adj[x][i].first]>dis3[x]+adj[x][i].second){
			dis3[adj[x][i].first]=dis3[x]+adj[x][i].second;
			lis.push({-dis3[adj[x][i].first],adj[x][i].first});
		}
	}
}
void dijkstra2(int x){
	for(int i=0;i<adj[x].size();i++){
		if(dis2[adj[x][i].first]>dis2[x]+adj[x][i].second){
			dis2[adj[x][i].first]=dis2[x]+adj[x][i].second;
			min1[adj[x][i].first]=min(min1[adj[x][i].first],min1[x]);
			min2[adj[x][i].first]=min(min2[adj[x][i].first],min2[x]);
			lis.push({-dis2[adj[x][i].first],adj[x][i].first});
		}
		else{
			if(dis2[adj[x][i].first]==dis2[x]+adj[x][i].second){
				min1[adj[x][i].first]=min(min1[adj[x][i].first],min1[x]);
				min2[adj[x][i].first]=min(min2[adj[x][i].first],min2[x]);
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,s,t,u,v,i,j,k,l;
	cin>>n>>m>>s>>t>>u>>v;
	for(i=1;i<=n;i++){
		dis[i]=inf;
		dis1[i]=inf;
		dis3[i]=inf;
		dis2[i]=inf;
	}
	for(i=1;i<=m;i++){
		cin>>j>>k>>l;
		adj[j].push_back({k,l});
		adj[k].push_back({j,l});
	}
	dis[u]=0;
	lis.push({0,u});
	while(lis.size()){
		if(-lis.top().first==dis[lis.top().second]){
			dijkstra(lis.top().second);
		}
		lis.pop();
	}
	dis1[v]=0;
	lis.push({0,v});
	while(lis.size()){
		if(-lis.top().first==dis1[lis.top().second]){
			dijkstra1(lis.top().second);
		}
		lis.pop();
	}
	dis3[t]=0;
	lis.push({0,t});
	while(lis.size()){
		if(-lis.top().first==dis3[lis.top().second]){
			dijkstra3(lis.top().second);
		}
		lis.pop();
	}	
	dis2[s]=0;
	lis.push({0,s});
	for(i=1;i<=n;i++){
		min1[i]=dis[i];
		min2[i]=dis1[i];
	}
	ans=dis[v];
	while(lis.size()){
		if(-lis.top().first==dis2[lis.top().second]){
			if(dis2[lis.top().second]+dis3[lis.top().second]==dis3[s]){
				ans=min(ans,min1[lis.top().second]+dis1[lis.top().second]);
				ans=min(ans,min2[lis.top().second]+dis[lis.top().second]);
				dijkstra2(lis.top().second);
			}
		}
		lis.pop();
	}
	cout<<ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int)':
commuter_pass.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(long long int)':
commuter_pass.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra3(long long int)':
commuter_pass.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra2(long long int)':
commuter_pass.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~

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