답안 #45646 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45646	2018-04-15T17:07:42 Z	reality	Commuter Pass (JOI18_commuter_pass)	C++17	55 / 100	887 ms	93604 KB

commuter_pass

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
#define int ll
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
ll D1[N];
ll D2[N];
ll D3[N];
ll D4[N];
vector < pii > g[N];
int n;
void Go(ll D[],int S) {
	for (int i = 1;i <= n;++i)
		D[i] = 1e18;
	D[S] = 0;
	priority_queue < pair < ll , int > , vector < pair < ll , int > > , greater < pair < ll , int > > > Q;
	Q.push(mp(0,S));
	while (!Q.empty()) {
		const ll cost = Q.top().fi;
		const int node = Q.top().se;
		Q.pop();
		if (cost != D[node])
			continue;
		for (auto it : g[node])
			if (D[it.fi] > D[node] + it.se)
				D[it.fi] = D[node] + it.se,Q.push(mp(D[it.fi],it.fi));
	}
}
ll ans = 1e18;
vi order;
vi G[2][N];
int was[N];
void go(ll d1[],ll d2[],int who) {
	static ll D[N];
	for (int i = 1;i <= n;++i)
		D[i] = d1[i];
	for (auto u : order)
		for (auto v : G[who][u])
			smin(D[u],D[v]);
	for (int i = 1;i <= n;++i)
		smin(ans,D[i] + d2[i]);
}
int32_t main(void)
{
    int m;
    int S,T,U,V;
    cin>>n>>m>>S>>T>>U>>V;
    while (m --) {
    	int a,b,c;
    	cin>>a>>b>>c;
    	g[a].pb(mp(b,c));
    	g[b].pb(mp(a,c));
    }
    Go(D1,S);
    Go(D2,T);
    Go(D3,U);
    Go(D4,V);
    queue < int > q;
    q.push(S);
    was[S] = 1;
    const ll dist = D1[T];
    while (!q.empty()) {
    	int node = q.front();
    	q.pop();
    	order.pb(node);
    	for (auto it : g[node])
    		if (D1[node] + it.se + D2[it.fi] == dist) {
    			G[0][node].pb(it.fi);
    			G[1][it.fi].pb(node);
    			if (!was[it.fi])
	    			was[it.fi] = 1,q.push(it.fi);
    		}
    }
    ans = D3[V];
    for (int cs = 0;cs < 2;++cs) {
	    go(D3,D4,cs);
	    go(D4,D3,cs);
	    reverse(all(order));
	    go(D3,D4,cs);
	    go(D4,D3,cs);
	    reverse(all(order));
	}
    cout << ans << '\n';
    return 0;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	644 ms	87484 KB	Output is correct
2	Correct	674 ms	87484 KB	Output is correct
3	Correct	745 ms	90656 KB	Output is correct
4	Correct	651 ms	90656 KB	Output is correct
5	Correct	686 ms	90656 KB	Output is correct
6	Correct	695 ms	90656 KB	Output is correct
7	Correct	728 ms	90656 KB	Output is correct
8	Correct	706 ms	90656 KB	Output is correct
9	Correct	651 ms	90656 KB	Output is correct
10	Correct	627 ms	90656 KB	Output is correct
11	Correct	370 ms	90656 KB	Output is correct
12	Correct	655 ms	90656 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	685 ms	90656 KB	Output is correct
2	Correct	706 ms	90656 KB	Output is correct
3	Correct	694 ms	90656 KB	Output is correct
4	Correct	733 ms	90656 KB	Output is correct
5	Correct	764 ms	90656 KB	Output is correct
6	Correct	730 ms	90656 KB	Output is correct
7	Correct	735 ms	90956 KB	Output is correct
8	Correct	723 ms	90956 KB	Output is correct
9	Correct	686 ms	90956 KB	Output is correct
10	Correct	826 ms	90956 KB	Output is correct
11	Correct	436 ms	90956 KB	Output is correct
12	Correct	887 ms	90956 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	90956 KB	Output is correct
2	Correct	66 ms	90956 KB	Output is correct
3	Correct	75 ms	90956 KB	Output is correct
4	Correct	160 ms	90956 KB	Output is correct
5	Correct	100 ms	90956 KB	Output is correct
6	Correct	74 ms	90956 KB	Output is correct
7	Correct	72 ms	90956 KB	Output is correct
8	Correct	83 ms	90956 KB	Output is correct
9	Correct	70 ms	90956 KB	Output is correct
10	Correct	92 ms	90956 KB	Output is correct
11	Correct	75 ms	90956 KB	Output is correct
12	Correct	67 ms	90956 KB	Output is correct
13	Correct	73 ms	90956 KB	Output is correct
14	Correct	65 ms	90956 KB	Output is correct
15	Correct	79 ms	90956 KB	Output is correct

Subtask #4
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	644 ms	87484 KB	Output is correct
2	Correct	674 ms	87484 KB	Output is correct
3	Correct	745 ms	90656 KB	Output is correct
4	Correct	651 ms	90656 KB	Output is correct
5	Correct	686 ms	90656 KB	Output is correct
6	Correct	695 ms	90656 KB	Output is correct
7	Correct	728 ms	90656 KB	Output is correct
8	Correct	706 ms	90656 KB	Output is correct
9	Correct	651 ms	90656 KB	Output is correct
10	Correct	627 ms	90656 KB	Output is correct
11	Correct	370 ms	90656 KB	Output is correct
12	Correct	655 ms	90656 KB	Output is correct
13	Correct	685 ms	90656 KB	Output is correct
14	Correct	706 ms	90656 KB	Output is correct
15	Correct	694 ms	90656 KB	Output is correct
16	Correct	733 ms	90656 KB	Output is correct
17	Correct	764 ms	90656 KB	Output is correct
18	Correct	730 ms	90656 KB	Output is correct
19	Correct	735 ms	90956 KB	Output is correct
20	Correct	723 ms	90956 KB	Output is correct
21	Correct	686 ms	90956 KB	Output is correct
22	Correct	826 ms	90956 KB	Output is correct
23	Correct	436 ms	90956 KB	Output is correct
24	Correct	887 ms	90956 KB	Output is correct
25	Correct	93 ms	90956 KB	Output is correct
26	Correct	66 ms	90956 KB	Output is correct
27	Correct	75 ms	90956 KB	Output is correct
28	Correct	160 ms	90956 KB	Output is correct
29	Correct	100 ms	90956 KB	Output is correct
30	Correct	74 ms	90956 KB	Output is correct
31	Correct	72 ms	90956 KB	Output is correct
32	Correct	83 ms	90956 KB	Output is correct
33	Correct	70 ms	90956 KB	Output is correct
34	Correct	92 ms	90956 KB	Output is correct
35	Correct	75 ms	90956 KB	Output is correct
36	Correct	67 ms	90956 KB	Output is correct
37	Correct	73 ms	90956 KB	Output is correct
38	Correct	65 ms	90956 KB	Output is correct
39	Correct	79 ms	90956 KB	Output is correct
40	Correct	753 ms	90956 KB	Output is correct
41	Correct	678 ms	90956 KB	Output is correct
42	Correct	692 ms	90956 KB	Output is correct
43	Correct	471 ms	90956 KB	Output is correct
44	Correct	480 ms	90956 KB	Output is correct
45	Correct	867 ms	93604 KB	Output is correct
46	Incorrect	769 ms	93604 KB	Output isn't correct
47	Halted	0 ms	0 KB	-

답안 #45646

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 0 / 45.0

Subtask #1
16.0 / 16.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
0 / 45.0