oj.uz

답안 #255568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255568 2020-08-01T09:20:43 Z tleontest1 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 822 ms 42888 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;
typedef pair< lo,PII > PIII;
typedef pair< lo,PIII > PIIII;
typedef pair< lo,PIIII > PIIIII;

#define fi first
#define se second
#define mp make_pair
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,u,v,s,visit[li],d[li],vis[li],deg[li],cost[li],cost1[li],mini[li],mini1[li],ans=inf;
int cev;
vector<PII> vec[li];

inline void sp(){
	priority_queue<PII> pq;
	pq.push({0,t});
	while(pq.size()){
		int node=pq.top().se;
		int co=-pq.top().fi;
		pq.pop();
		if(vis[node])continue;
		vis[node]=1;
		d[node]=co;
		for(int i=0;i<(int)vec[node].size();i++){
			int go=vec[node][i].fi;
			int ind=vec[node][i].se;
			pq.push({-co-a[ind],go});
		}
	}
	//~ cout<<d[s]<<endl;
	memset(vis,0,sizeof(vis));
	pq.push({0,s});
	while(pq.size()){
		int node=pq.top().se;
		int co=-pq.top().fi;
		pq.pop();
		if(vis[node])continue;
		vis[node]=1;
		deg[node]=co;
		for(int i=0;i<(int)vec[node].size();i++){
			int go=vec[node][i].fi;
			int ind=vec[node][i].se;
			//~ cout<<go<<" : : "<<co<<" : : "<<d[go]<<" : : "<<a[ind]<<endl;
			if(d[go]+co+a[ind]==d[s])visit[ind]=1;
			pq.push({-co-a[ind],go});
		}
	}
	memset(vis,0,sizeof(vis));
	pq.push({0,u});
	while(pq.size()){
		int node=pq.top().se;
		int co=-pq.top().fi;
		pq.pop();
		if(vis[node])continue;
		vis[node]=1;
		cost[node]=co;
		for(int i=0;i<(int)vec[node].size();i++){
			int go=vec[node][i].fi;
			int ind=vec[node][i].se;
			//~ cout<<go<<" : : "<<co<<" : : "<<d[go]<<" : : "<<a[ind]<<endl;
			if(d[go]+co+a[ind]==d[s])visit[ind]=1;
			pq.push({-co-a[ind],go});
		}
	}
	memset(vis,0,sizeof(vis));
	pq.push({0,v});
	while(pq.size()){
		int node=pq.top().se;
		int co=-pq.top().fi;
		pq.pop();
		if(vis[node])continue;
		vis[node]=1;
		cost1[node]=co;
		for(int i=0;i<(int)vec[node].size();i++){
			int go=vec[node][i].fi;
			int ind=vec[node][i].se;
			//~ cout<<go<<" : : "<<co<<" : : "<<d[go]<<" : : "<<a[ind]<<endl;
			if(d[go]+co+a[ind]==d[s])visit[ind]=1;
			pq.push({-co-a[ind],go});
		}
	}
	priority_queue<PIIIII> pq1;
	memset(vis,0,sizeof(vis));
	pq1.push({0,{-cost[s]-cost1[s],{-cost[s],{-cost1[s],s}}}});
	while(pq1.size()){
		//~ int node=pq1.top().se.se;
		int node=pq1.top().se.se.se.se;
		int co2=-pq1.top().se.se.se.fi;
		int co1=-pq1.top().se.se.fi;
		int cooo=-pq1.top().se.fi;
		int co=-pq1.top().fi;
		pq1.pop();
		if(vis[node])continue;
		vis[node]=1;
		ans=min(ans,co1+co2);
		for(int i=0;i<(int)vec[node].size();i++){
			int go=vec[node][i].fi;
			int ind=vec[node][i].se;
			if(d[go]+co+a[ind]==d[s] && deg[node]+d[go]+a[ind]==deg[t]){
				pq1.push({-co-a[ind],{-min(co1,cost[go])-min(co2,cost1[go]),{-min(co1,cost[go]),{-min(co2,cost1[go]),go}}}});
			}
		}
	}
	
}

main(void){
	scanf("%lld %lld",&n,&m);
	scanf("%lld %lld",&s,&t);
	scanf("%lld %lld",&u,&v);
	FOR mini[i]=inf;
	FOR mini1[i]=inf;
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%lld %lld %lld",&x,&y,&a[i]);
		vec[x].pb({y,i});
		vec[y].pb({x,i});
	}
	sp();
	//~ int ans=inf;
	//~ FOR{
		//~ ans=min(ans,mini[i]+mini1[i]);
		//~ ////~ cout<<mini[i]+mini1[i]<<" : : "<<mini[i]<<" : : "<<mini1[i]<<endl;
	//~ }
	ans=min(ans,cost[v]);
	printf("%lld\n",ans);
	return 0;
}

Compilation message

commuter_pass.cpp: In function 'void sp()':
commuter_pass.cpp:113:7: warning: unused variable 'cooo' [-Wunused-variable]
   int cooo=-pq1.top().se.fi;
       ^~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:130:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&s,&t);
  ~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&u,&v);
  ~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&x,&y,&a[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 726 ms 35556 KB Output is correct
2 Correct 725 ms 36704 KB Output is correct
3 Correct 750 ms 36832 KB Output is correct
4 Correct 728 ms 35036 KB Output is correct
5 Correct 725 ms 36836 KB Output is correct
6 Correct 682 ms 35420 KB Output is correct
7 Correct 790 ms 36956 KB Output is correct
8 Correct 761 ms 36960 KB Output is correct
9 Correct 665 ms 35504 KB Output is correct
10 Correct 661 ms 35420 KB Output is correct
11 Correct 193 ms 27512 KB Output is correct
12 Correct 647 ms 35548 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 672 ms 36868 KB Output is correct
2 Correct 626 ms 37988 KB Output is correct
3 Correct 599 ms 36832 KB Output is correct
4 Correct 721 ms 36452 KB Output is correct
5 Correct 755 ms 36328 KB Output is correct
6 Correct 665 ms 36860 KB Output is correct
7 Correct 760 ms 38500 KB Output is correct
8 Correct 755 ms 36456 KB Output is correct
9 Correct 736 ms 37736 KB Output is correct
10 Correct 648 ms 36576 KB Output is correct
11 Correct 202 ms 27512 KB Output is correct
12 Correct 660 ms 36828 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 18600 KB Output is correct
2 Correct 12 ms 16128 KB Output is correct
3 Correct 12 ms 16128 KB Output is correct
4 Correct 89 ms 19956 KB Output is correct
5 Correct 46 ms 18424 KB Output is correct
6 Correct 12 ms 16128 KB Output is correct
7 Correct 16 ms 16256 KB Output is correct
8 Correct 16 ms 16384 KB Output is correct
9 Correct 14 ms 16256 KB Output is correct
10 Correct 50 ms 18684 KB Output is correct
11 Correct 12 ms 16128 KB Output is correct
12 Correct 13 ms 16128 KB Output is correct
13 Correct 16 ms 16128 KB Output is correct
14 Correct 12 ms 16128 KB Output is correct
15 Correct 16 ms 16128 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 726 ms 35556 KB Output is correct
2 Correct 725 ms 36704 KB Output is correct
3 Correct 750 ms 36832 KB Output is correct
4 Correct 728 ms 35036 KB Output is correct
5 Correct 725 ms 36836 KB Output is correct
6 Correct 682 ms 35420 KB Output is correct
7 Correct 790 ms 36956 KB Output is correct
8 Correct 761 ms 36960 KB Output is correct
9 Correct 665 ms 35504 KB Output is correct
10 Correct 661 ms 35420 KB Output is correct
11 Correct 193 ms 27512 KB Output is correct
12 Correct 647 ms 35548 KB Output is correct
13 Correct 672 ms 36868 KB Output is correct
14 Correct 626 ms 37988 KB Output is correct
15 Correct 599 ms 36832 KB Output is correct
16 Correct 721 ms 36452 KB Output is correct
17 Correct 755 ms 36328 KB Output is correct
18 Correct 665 ms 36860 KB Output is correct
19 Correct 760 ms 38500 KB Output is correct
20 Correct 755 ms 36456 KB Output is correct
21 Correct 736 ms 37736 KB Output is correct
22 Correct 648 ms 36576 KB Output is correct
23 Correct 202 ms 27512 KB Output is correct
24 Correct 660 ms 36828 KB Output is correct
25 Correct 59 ms 18600 KB Output is correct
26 Correct 12 ms 16128 KB Output is correct
27 Correct 12 ms 16128 KB Output is correct
28 Correct 89 ms 19956 KB Output is correct
29 Correct 46 ms 18424 KB Output is correct
30 Correct 12 ms 16128 KB Output is correct
31 Correct 16 ms 16256 KB Output is correct
32 Correct 16 ms 16384 KB Output is correct
33 Correct 14 ms 16256 KB Output is correct
34 Correct 50 ms 18684 KB Output is correct
35 Correct 12 ms 16128 KB Output is correct
36 Correct 13 ms 16128 KB Output is correct
37 Correct 16 ms 16128 KB Output is correct
38 Correct 12 ms 16128 KB Output is correct
39 Correct 16 ms 16128 KB Output is correct
40 Correct 720 ms 39136 KB Output is correct
41 Correct 822 ms 39900 KB Output is correct
42 Correct 648 ms 39648 KB Output is correct
43 Correct 364 ms 29560 KB Output is correct
44 Correct 232 ms 29560 KB Output is correct
45 Correct 739 ms 42724 KB Output is correct
46 Correct 710 ms 42340 KB Output is correct
47 Correct 630 ms 39012 KB Output is correct
48 Correct 236 ms 29048 KB Output is correct
49 Correct 613 ms 37980 KB Output is correct
50 Correct 678 ms 42888 KB Output is correct
51 Correct 817 ms 42656 KB Output is correct