oj.uz

Submission #228972

# Submission time Handle Problem Language Result Execution time Memory
228972 2020-05-03T08:11:24 Z bharat2002 Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 637 ms 36600 KB 
/*input
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
int n, m, s, t, u, v, dists[N], distt[N];
vector< pii > adjlist[N];
priority_queue< pii, vector<pii>, greater<pii> >pq1;int dp[N][4];
void dij(int src, int dist[N])
{
	for(int i=1;i<=n;i++) {dist[i]=inf;dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=inf;}
	dist[src]=0;pq1.push(mp(0, src));
	while(!pq1.empty())
	{
		pii cur=pq1.top();pq1.pop();
		if(cur.f>dist[cur.s]) continue;
		for(auto j:adjlist[cur.s])
		{
			if(dist[j.f]>cur.f + j.s)
			{
				dist[j.f]=cur.f+j.s;pq1.push(mp(dist[j.f], j.f));
			}
		}
	}
}
struct node
{
	int i, j, cd;
};
node mn(int a, int b, int c)
{
	node t;t.i=a;t.j=b;t.cd=c;return t;
}
struct comp
{
	bool operator()(node a, node b)
	{
		if(a.cd==b.cd) return (b.j==1);
		return a.cd>=b.cd;
	}
};
priority_queue<node, vector<node>, comp> pq;
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m>>s>>t>>u>>v;
	for(int i=1;i<=m;i++)
	{
		int u, v, w;cin>>u>>v>>w;adjlist[u].push_back(mp(v, w));adjlist[v].push_back(mp(u, w));
	}
	dij(s, dists);dij(t, distt);
	dp[u][0]=dp[u][1]=dp[u][2]=dp[u][3]=0;pq.push(mn(u, 0, 0));pq.push(mn(u, 1, 0));pq.push(mn(u, 2, 0));
	while(!pq.empty())
	{

		node cur=pq.top();pq.pop();//cout<<cur.i<<" "<<cur.j<<endl;
		if(cur.cd>dp[cur.i][cur.j]) continue;
		for(auto j:adjlist[cur.i])
		{
			bool check=(dists[cur.i]+j.s+distt[j.f]==dists[t]||distt[cur.i]+j.s+dists[j.f]==dists[t]);
			if(cur.j==1) {
				if(check&&dists[j.f]<dists[cur.i]) {j.s=0;
					if(dp[j.f][1]>cur.cd +j.s)
					{
						dp[j.f][1]=cur.cd +j.s;pq.push(mn(j.f, 1, cur.cd +j.s));
					}
				}
			}
			if(cur.j==2)
			{
				if(check&&dists[j.f]>dists[cur.i]) {j.s=0;
					if(dp[j.f][2]>cur.cd +j.s)
					{
						dp[j.f][2]=cur.cd +j.s;pq.push(mn(j.f, 2, cur.cd +j.s));
					}
				}
			}
			if(cur.j==0)
			{
				for(int nxt=0;nxt<3;nxt++)
				{
					if(dp[j.f][nxt]>cur.cd +j.s)
					{
						dp[j.f][nxt]=cur.cd +j.s;pq.push(mn(j.f, nxt, cur.cd +j.s));
					}
				}
			}
			if(dp[j.f][3]>cur.cd +j.s)
			{
				dp[j.f][3]=cur.cd +j.s;pq.push(mn(j.f, 3, cur.cd +j.s));continue;
			}
		}
	}
	cout<<min(min(dp[v][1], dp[v][2]), dp[v][3]);
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 33764 KB Output is correct
2 Correct 543 ms 26804 KB Output is correct
3 Correct 468 ms 27540 KB Output is correct
4 Correct 447 ms 26600 KB Output is correct
5 Correct 457 ms 26332 KB Output is correct
6 Correct 539 ms 33756 KB Output is correct
7 Correct 596 ms 26472 KB Output is correct
8 Correct 509 ms 26596 KB Output is correct
9 Correct 530 ms 26472 KB Output is correct
10 Correct 423 ms 26204 KB Output is correct
11 Correct 164 ms 13560 KB Output is correct
12 Correct 584 ms 26360 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 26760 KB Output is correct
2 Correct 534 ms 26596 KB Output is correct
3 Correct 574 ms 26588 KB Output is correct
4 Correct 548 ms 26600 KB Output is correct
5 Correct 544 ms 26824 KB Output is correct
6 Correct 469 ms 26848 KB Output is correct
7 Correct 603 ms 32860 KB Output is correct
8 Correct 637 ms 26724 KB Output is correct
9 Correct 541 ms 26852 KB Output is correct
10 Correct 587 ms 26728 KB Output is correct
11 Correct 178 ms 13816 KB Output is correct
12 Correct 477 ms 27052 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4480 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 25 ms 6144 KB Output is correct
5 Correct 15 ms 4480 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 10 ms 2944 KB Output is correct
8 Correct 9 ms 3072 KB Output is correct
9 Correct 7 ms 2944 KB Output is correct
10 Correct 15 ms 4480 KB Output is correct
11 Correct 6 ms 2816 KB Output is correct
12 Correct 7 ms 2816 KB Output is correct
13 Correct 6 ms 2816 KB Output is correct
14 Correct 7 ms 2816 KB Output is correct
15 Correct 8 ms 2944 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 33764 KB Output is correct
2 Correct 543 ms 26804 KB Output is correct
3 Correct 468 ms 27540 KB Output is correct
4 Correct 447 ms 26600 KB Output is correct
5 Correct 457 ms 26332 KB Output is correct
6 Correct 539 ms 33756 KB Output is correct
7 Correct 596 ms 26472 KB Output is correct
8 Correct 509 ms 26596 KB Output is correct
9 Correct 530 ms 26472 KB Output is correct
10 Correct 423 ms 26204 KB Output is correct
11 Correct 164 ms 13560 KB Output is correct
12 Correct 584 ms 26360 KB Output is correct
13 Correct 557 ms 26760 KB Output is correct
14 Correct 534 ms 26596 KB Output is correct
15 Correct 574 ms 26588 KB Output is correct
16 Correct 548 ms 26600 KB Output is correct
17 Correct 544 ms 26824 KB Output is correct
18 Correct 469 ms 26848 KB Output is correct
19 Correct 603 ms 32860 KB Output is correct
20 Correct 637 ms 26724 KB Output is correct
21 Correct 541 ms 26852 KB Output is correct
22 Correct 587 ms 26728 KB Output is correct
23 Correct 178 ms 13816 KB Output is correct
24 Correct 477 ms 27052 KB Output is correct
25 Correct 16 ms 4480 KB Output is correct
26 Correct 6 ms 2816 KB Output is correct
27 Correct 6 ms 2816 KB Output is correct
28 Correct 25 ms 6144 KB Output is correct
29 Correct 15 ms 4480 KB Output is correct
30 Correct 7 ms 2816 KB Output is correct
31 Correct 10 ms 2944 KB Output is correct
32 Correct 9 ms 3072 KB Output is correct
33 Correct 7 ms 2944 KB Output is correct
34 Correct 15 ms 4480 KB Output is correct
35 Correct 6 ms 2816 KB Output is correct
36 Correct 7 ms 2816 KB Output is correct
37 Correct 6 ms 2816 KB Output is correct
38 Correct 7 ms 2816 KB Output is correct
39 Correct 8 ms 2944 KB Output is correct
40 Correct 564 ms 36600 KB Output is correct
41 Correct 502 ms 29792 KB Output is correct
42 Correct 520 ms 29920 KB Output is correct
43 Correct 197 ms 15096 KB Output is correct
44 Correct 225 ms 15604 KB Output is correct
45 Correct 466 ms 25696 KB Output is correct
46 Correct 474 ms 28392 KB Output is correct
47 Correct 507 ms 30308 KB Output is correct
48 Correct 204 ms 14520 KB Output is correct
49 Correct 418 ms 36060 KB Output is correct
50 Correct 445 ms 28772 KB Output is correct
51 Correct 431 ms 25700 KB Output is correct