Submission #66750

#	Time	Username	Problem	Language	Result	Execution time	Memory
66750		hamzqq9	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	830 ms	45960 KiB

commuter_pass

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 100000000000000
#define MOD 1000000007
#define N 100005
#define MAX 10000006
#define LOG 22
using namespace std;

struct state {

	ll cost;
	int from,now;

	bool operator<(const state& oth) const {

		return cost>oth.cost;

	}

	state(ll x,int y,int z) {

		cost=x;
		from=y;
		now=z;

	}

};

int n,m,S,T,U,V,x,y,z;
int mark[N],in[N];
ll up_min[2][N],SH[3][N];
ll ans=inf;
vector<int> graf1[N],graf2[N];
vector<ii> v[N];

void dfs_str(int node) {

//	printf("Node --> %d\n",node);

//	printf("up_min[0][%d] --> %lld up_min[1][%d] --> %lld\n",node,up_min[0][node],node,up_min[1][node]);

	umin(ans,up_min[0][node]+SH[2][node]);

	umin(ans,up_min[1][node]+SH[1][node]);

	umin(up_min[0][node],SH[1][node]);

	umin(up_min[1][node],SH[2][node]);

//	printf("Changed up_min[0][%d] --> %lld up_min[1][%d] --> %lld\n",node,up_min[0][node],node,up_min[1][node]);

	for(int go:graf1[node]) {

		in[go]--;

		umin(up_min[0][go],up_min[0][node]);
		umin(up_min[1][go],up_min[1][node]);

		if(!in[go] && mark[go]) {

			dfs_str(go);

		}

	}

}

void dfs_rev(int node) {

//	printf("Node Mark --> %d\n",node);

	if(mark[node]) {
	
//		printf("Returned --> %d\n",node);

		return ;
	
	}

	mark[node]=1;

	for(int go:graf2[node]) {

//		printf("Cur Node --> %d\n",node);

		dfs_rev(go);

	}

}

void shp(int node,int wa,int add) {

	priority_queue<state> Q;

	Q.push(state(0,-1,node));

	for(int i=1;i<=n;i++) SH[wa][i]=inf;

	while(!Q.empty()) {

		state result=Q.top();

		Q.pop();

		if(SH[wa][result.now]!=inf) {

			if(SH[wa][result.now]==result.cost && add && result.from!=-1) {

				graf1[result.from].pb(result.now);
				graf2[result.now].pb(result.from);

			}

			continue ;

		}

		SH[wa][result.now]=result.cost;

		if(result.from!=-1 && add) {

			graf1[result.from].pb(result.now);
			graf2[result.now].pb(result.from);

		}

		for(ii go:v[result.now]) {

			Q.push(state(result.cost+go.nd,result.now,go.st));

		}

	}

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d %d",&n,&m);

	scanf("%d %d",&S,&T);

	scanf("%d %d",&U,&V);

	for(int i=1;i<=m;i++) {

		scanf("%d %d %d",&x,&y,&z);

		v[x].pb({y,z});
		v[y].pb({x,z});

	}

	shp(S,0,1); // from  which array  add edge?
	shp(U,1,0);
	shp(V,2,0);

	/*for(int i=0;i<3;i++) {

		if(i==0) printf("FROM S\n");
		else if(i==1) printf("FROM U\n");
		else printf("FROM V\n");

		for(int j=1;j<=n;j++) printf("%d %lld\n",j,SH[i][j]);

	}*/

	dfs_rev(T);

	for(int i=1;i<=n;i++) {

		if(mark[i]) {

			for(int go:graf1[i]) {

				in[go]++;

			}

		}

		up_min[0][i]=up_min[1][i]=inf;

	}

	dfs_str(S);

	printf("%lld\n",min(ans,SH[1][V]));

}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&S,&T);
  ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:163:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&U,&V);
  ~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&y,&z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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