Submission #1083957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083957		Newtonabc	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	381 ms	58824 KiB

commuter_pass

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1e5+10;
bool vs[4*N];
long long dista[N],distb[N],dist[4*N];
vector<pair<long long,int> > adj[4*N];
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m,s,t,st,ed;
	cin>>n >>m >>s >>t >>st >>ed;
	for(int i=0;i<m;i++){
		int a,b;
		long long c;
		cin>>a >>b >>c;
		adj[a].push_back(mp(c,b));
		adj[b].push_back(mp(c,a));
		adj[3*n+a].push_back(mp(c,3*n+b));
		adj[3*n+b].push_back(mp(c,3*n+a));
	}
	for(int i=1;i<=n;i++) dista[i]=LLONG_MAX,distb[i]=LLONG_MAX;
	dista[s]=0,distb[t]=0;
	q.push(mp(0,s));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vs[u]) continue;
		vs[u]=true;
		for(int i=0;i<adj[u].size();i++){
			int v=adj[u][i].second;
			long long w=adj[u][i].first;
			if(dista[u]+w<dista[v]){
				dista[v]=dista[u]+w;
				q.push(mp(dista[v],v));
			}
		}
	}
	for(int i=1;i<=n;i++) vs[i]=false;
	q.push(mp(0,t));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vs[u]) continue;
		vs[u]=true;
		for(int i=0;i<adj[u].size();i++){
			int v=adj[u][i].second;
			long long w=adj[u][i].first;
			if(distb[u]+w<distb[v]){
				distb[v]=distb[u]+w;
				q.push(mp(distb[v],v));
			}
		}
	}
	/*for(int i=1;i<=n;i++) cout<<dista[i] <<" ";
	cout<<"\n";
	for(int i=1;i<=n;i++) cout<<distb[i] <<" ";*/
	for(int u=1;u<=n;u++){
		adj[u].push_back(mp(0,n+u));
		adj[u].push_back(mp(0,2*n+u));
		adj[n+u].push_back(mp(0,3*n+u));
		adj[2*n+u].push_back(mp(0,3*n+u));
		for(int i=0;i<adj[u].size();i++){
			int v=adj[u][i].second;
			long long w=adj[u][i].first;
			if(v>n) continue;
			if(dista[u]+w+distb[v]==dista[t]){
				adj[n+u].push_back(mp(0,n+v));
				adj[2*n+v].push_back(mp(0,2*n+u));
			}
		}
	}
	for(int i=1;i<=4*n;i++) dist[i]=LLONG_MAX,vs[i]=false;
	dist[st]=0;
	q.push(mp(0,st));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vs[u]) continue;
		vs[u]=true;
		for(int i=0;i<adj[u].size();i++){
			int v=adj[u][i].second;
			long long w=adj[u][i].first;
			if(dist[u]+w<dist[v]){
				dist[v]=dist[u]+w;
				q.push(mp(dist[v],v));
			}
		}
	}
	cout<<dist[3*n+ed];
	/*for(int i=1;i<=4*n;i++){
		for(int j=0;j<adj[i].size();j++){
			cout<<i <<" " <<adj[i][j].second <<" " <<adj[i][j].first <<"\n";
		}
	}*/
	
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
commuter_pass.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
commuter_pass.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
commuter_pass.cpp:82:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~

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