답안 #487098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487098	2021-11-14T06:04:35 Z	PoPularPlusPlus	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	262 ms	24424 KB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

const int N = 100002;
vector<pair<int,ll>> adj[N];
ll dis[N];

void mem(){
	for(int i = 0; i < N; i++)dis[i] = 1e18;
}

void Dijkstra(ll e){
	 priority_queue< pair<ll,ll>, vector <pair<ll,ll>> , greater<pair<ll,ll>> > pq; 
	 dis[e]=0;
	 pq.push({0,e});
	 while(!pq.empty()){
		 ll node = pq.top().second,ww=pq.top().first;
		 pq.pop();
		 if(dis[node] < ww)continue;
		 for(auto i : adj[node]){
			 ll w = i.second;
			 if(dis[i.first] > dis[node] + w){
				 dis[i.first] = dis[node] + w;
				 pq.push({dis[i.first],i.first});
			 }
		 }
	 }
}

void solve(){
	int n , m;
	cin >> n >> m;
	int s , t;
	cin >> s >> t;
	int a , b;
	cin >> a >> b;
	for(int i = 0; i < m; i++){
		ll x , y , z;
		cin >> x >> y >> z;
		adj[x].pb(mp(y,z));
		adj[y].pb(mp(x,z));
	}
	ll dis1[N] , dis2[N];
	mem();
	Dijkstra(a);
	for(int i = 0; i <= n; i++)dis1[i] = dis[i];
	mem();
	Dijkstra(b);
	for(int i = 0; i <= n; i++)dis2[i] = dis[i];
	mem();
	Dijkstra(s);
	ll mn[N] , mx[N];
	for(int i = 0; i <= n; i++)mn[i] = dis1[i];
	for(int i = 0; i <= n; i++)mx[i] = dis2[i];
	queue<int> q;
	bool vis[N];
	memset(vis,0,sizeof vis);
	vis[t] = 1;
	q.push(t);
	int cnt[N];
	memset(cnt,0,sizeof cnt);
	while(q.size()){
		int node = q.front();
		q.pop();
		for(auto i : adj[node]){
			if(dis[i.vf] + i.vs == dis[node]){
				cnt[i.vf]++;
				if(!vis[i.vf]){
					vis[i.vf] = 1;
					q.push(i.vf);
				}
			}
		}
	}
	ll ans = dis1[b];
	q.push(t);
	while(q.size()){
		int node = q.front();
		q.pop();
		ans = min(ans , min(dis1[node] + mx[node] , dis2[node] + mn[node]));
		for(auto i : adj[node]){
			if(dis[i.vf] == dis[node] - i.vs){
				mn[i.vf] = min(mn[i.vf] , mn[node]);
				mx[i.vf] = min(mx[i.vf] , mx[node]);
				cnt[i.vf]--;
				if(cnt[i.vf] == 0){
					q.push(i.vf);
				}
			}
		}
	}
	cout << ans << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	262 ms	20532 KB	Output is correct
2	Correct	235 ms	19384 KB	Output is correct
3	Correct	241 ms	18996 KB	Output is correct
4	Correct	211 ms	20476 KB	Output is correct
5	Correct	226 ms	19264 KB	Output is correct
6	Correct	261 ms	20648 KB	Output is correct
7	Correct	238 ms	19452 KB	Output is correct
8	Correct	223 ms	22808 KB	Output is correct
9	Correct	214 ms	23532 KB	Output is correct
10	Correct	204 ms	23536 KB	Output is correct
11	Correct	87 ms	14280 KB	Output is correct
12	Correct	219 ms	23504 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	248 ms	19512 KB	Output is correct
2	Correct	240 ms	19328 KB	Output is correct
3	Correct	221 ms	19320 KB	Output is correct
4	Correct	240 ms	19344 KB	Output is correct
5	Correct	262 ms	19332 KB	Output is correct
6	Correct	221 ms	19152 KB	Output is correct
7	Correct	254 ms	19424 KB	Output is correct
8	Correct	243 ms	19520 KB	Output is correct
9	Correct	230 ms	19344 KB	Output is correct
10	Correct	241 ms	19432 KB	Output is correct
11	Correct	98 ms	12292 KB	Output is correct
12	Correct	233 ms	19132 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	8396 KB	Output is correct
2	Correct	3 ms	7056 KB	Output is correct
3	Correct	3 ms	6988 KB	Output is correct
4	Correct	19 ms	10520 KB	Output is correct
5	Correct	9 ms	8780 KB	Output is correct
6	Correct	6 ms	7116 KB	Output is correct
7	Correct	6 ms	7244 KB	Output is correct
8	Correct	5 ms	7320 KB	Output is correct
9	Correct	4 ms	7116 KB	Output is correct
10	Correct	11 ms	8728 KB	Output is correct
11	Correct	4 ms	6988 KB	Output is correct
12	Correct	3 ms	7060 KB	Output is correct
13	Correct	3 ms	6988 KB	Output is correct
14	Correct	4 ms	7116 KB	Output is correct
15	Correct	4 ms	7064 KB	Output is correct

Subtask #4
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	262 ms	20532 KB	Output is correct
2	Correct	235 ms	19384 KB	Output is correct
3	Correct	241 ms	18996 KB	Output is correct
4	Correct	211 ms	20476 KB	Output is correct
5	Correct	226 ms	19264 KB	Output is correct
6	Correct	261 ms	20648 KB	Output is correct
7	Correct	238 ms	19452 KB	Output is correct
8	Correct	223 ms	22808 KB	Output is correct
9	Correct	214 ms	23532 KB	Output is correct
10	Correct	204 ms	23536 KB	Output is correct
11	Correct	87 ms	14280 KB	Output is correct
12	Correct	219 ms	23504 KB	Output is correct
13	Correct	248 ms	19512 KB	Output is correct
14	Correct	240 ms	19328 KB	Output is correct
15	Correct	221 ms	19320 KB	Output is correct
16	Correct	240 ms	19344 KB	Output is correct
17	Correct	262 ms	19332 KB	Output is correct
18	Correct	221 ms	19152 KB	Output is correct
19	Correct	254 ms	19424 KB	Output is correct
20	Correct	243 ms	19520 KB	Output is correct
21	Correct	230 ms	19344 KB	Output is correct
22	Correct	241 ms	19432 KB	Output is correct
23	Correct	98 ms	12292 KB	Output is correct
24	Correct	233 ms	19132 KB	Output is correct
25	Correct	10 ms	8396 KB	Output is correct
26	Correct	3 ms	7056 KB	Output is correct
27	Correct	3 ms	6988 KB	Output is correct
28	Correct	19 ms	10520 KB	Output is correct
29	Correct	9 ms	8780 KB	Output is correct
30	Correct	6 ms	7116 KB	Output is correct
31	Correct	6 ms	7244 KB	Output is correct
32	Correct	5 ms	7320 KB	Output is correct
33	Correct	4 ms	7116 KB	Output is correct
34	Correct	11 ms	8728 KB	Output is correct
35	Correct	4 ms	6988 KB	Output is correct
36	Correct	3 ms	7060 KB	Output is correct
37	Correct	3 ms	6988 KB	Output is correct
38	Correct	4 ms	7116 KB	Output is correct
39	Correct	4 ms	7064 KB	Output is correct
40	Correct	217 ms	24424 KB	Output is correct
41	Correct	214 ms	23504 KB	Output is correct
42	Correct	220 ms	23592 KB	Output is correct
43	Correct	103 ms	14416 KB	Output is correct
44	Correct	102 ms	14404 KB	Output is correct
45	Correct	257 ms	22492 KB	Output is correct
46	Correct	250 ms	22052 KB	Output is correct
47	Correct	220 ms	24220 KB	Output is correct
48	Correct	114 ms	13824 KB	Output is correct
49	Correct	236 ms	23892 KB	Output is correct
50	Correct	224 ms	22556 KB	Output is correct
51	Correct	226 ms	22288 KB	Output is correct

답안 #487098

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 45.0 / 45.0

Subtask #1
16.0 / 16.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
45.0 / 45.0