oj.uz

Submission #45185

# Submission time Handle Problem Language Result Execution time Memory
45185 2018-04-11T17:36:26 Z Pajaraja Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 867 ms 83920 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> g[100007],h[100007],k[100007];
vector<long long> w[100007];
long long d[3][100007],dpl[2][100007],dpd[2][100007];
int n,degin[100007],ord[100007],cur;
bool st[100007];
void djikstra(int s,int a)
{
	priority_queue<pair<long long,int> > pq;
	fill(d[a],d[a]+100007,-1LL);
	d[a][s]=0;
	for(int i=0;i<g[s].size();i++) pq.push(make_pair(-w[s][i],g[s][i]));
	while(!pq.empty())
	{
		long long t=-pq.top().first;
		int x=pq.top().second;
		pq.pop();
		if(d[a][x]==-1)
		{
			d[a][x]=t;
			for(int i=0;i<g[x].size();i++) pq.push(make_pair(-t-w[x][i],g[x][i]));
		}
	}
}
void praviDAG(int s,int a)
{
	priority_queue<pair<long long,pair<int,int> > > pq;
	fill(d[a],d[a]+100007,-1);
	d[a][s]=0;
	for(int i=0;i<g[s].size();i++) pq.push(make_pair(-w[s][i],make_pair(g[s][i],s)));
	while(!pq.empty())
	{
		long long t=-pq.top().first;
		int x=pq.top().second.first,y=pq.top().second.second;
		pq.pop();
		if(d[a][x]==-1)
		{
			d[a][x]=t;
			for(int i=0;i<g[x].size();i++) pq.push(make_pair(-t-w[x][i],make_pair(g[x][i],x)));
		}
		if(d[a][x]==t) 
		{
			h[y].push_back(x);
			k[x].push_back(y);
		}
	}
}
void toposort()
{
	queue<int> q;
	for(int i=1;i<=n;i++) degin[i]=k[i].size();
	for(int i=1;i<=n;i++) if(degin[i]==0) q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		ord[cur++]=u;
		q.pop();
		for(int i=0;i<h[u].size();i++) 
		{
			degin[h[u][i]]--;
			if(degin[h[u][i]]==0) q.push(h[u][i]); 
		}
	}
}
int main()
{
	int m,s,t,u,v;
	scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
	for(int i=0;i<m;i++)
	{
		int t1,t2;
		long long t3;
		scanf("%d%d%lld",&t1,&t2,&t3);
		g[t1].push_back(t2);
		g[t2].push_back(t1);
		w[t1].push_back(t3);
		w[t2].push_back(t3);
	}
	djikstra(u,0);
	djikstra(v,1);
	praviDAG(s,2);
	toposort();
	for(int i=0;i<cur;i++)
	{
		dpl[0][ord[i]]=d[0][ord[i]];
		dpl[1][ord[i]]=d[1][ord[i]];
		for(int j=0;j<k[ord[i]].size();j++)
		{
			dpl[0][ord[i]]=fmin(dpl[0][ord[i]],dpl[0][k[ord[i]][j]]);
			dpl[1][ord[i]]=fmin(dpl[1][ord[i]],dpl[1][k[ord[i]][j]]);
		}
	}
	st[t]=true;
	for(int i=cur-1;i>=0;i--)
	{
		dpd[0][ord[i]]=d[0][ord[i]];
		dpd[1][ord[i]]=d[1][ord[i]];
		for(int j=0;j<h[ord[i]].size();j++) if(st[h[ord[i]][j]])
		{
			st[ord[i]]=true;
			dpd[0][ord[i]]=fmin(dpd[0][ord[i]],dpd[0][h[ord[i]][j]]);
			dpd[1][ord[i]]=fmin(dpd[1][ord[i]],dpd[1][h[ord[i]][j]]);
		}
	}
	long long minimum=d[0][v];
	for(int i=1;i<=n;i++) if(st[i]) minimum=fmin(minimum,dpd[0][i]+dpl[1][i]);
	for(int i=1;i<=n;i++) if(st[i]) minimum=fmin(minimum,dpd[1][i]+dpl[0][i]);
	printf("%lld",minimum);
}

Compilation message

commuter_pass.cpp: In function 'void djikstra(int, int)':
commuter_pass.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) pq.push(make_pair(-w[s][i],g[s][i]));
              ~^~~~~~~~~~~~
commuter_pass.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<g[x].size();i++) pq.push(make_pair(-t-w[x][i],g[x][i]));
                ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void praviDAG(int, int)':
commuter_pass.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) pq.push(make_pair(-w[s][i],make_pair(g[s][i],s)));
              ~^~~~~~~~~~~~
commuter_pass.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<g[x].size();i++) pq.push(make_pair(-t-w[x][i],make_pair(g[x][i],x)));
                ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void toposort()':
commuter_pass.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<h[u].size();i++) 
               ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<k[ord[i]].size();j++)
               ~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:99:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<h[ord[i]].size();j++) if(st[h[ord[i]][j]])
               ~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld",&t1,&t2,&t3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 825 ms 33236 KB Output is correct
2 Correct 812 ms 35080 KB Output is correct
3 Correct 725 ms 35080 KB Output is correct
4 Correct 867 ms 35080 KB Output is correct
5 Correct 771 ms 35080 KB Output is correct
6 Correct 793 ms 35080 KB Output is correct
7 Correct 800 ms 35796 KB Output is correct
8 Correct 824 ms 36000 KB Output is correct
9 Correct 837 ms 36000 KB Output is correct
10 Correct 740 ms 37872 KB Output is correct
11 Correct 315 ms 37872 KB Output is correct
12 Correct 783 ms 45120 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 45120 KB Output is correct
2 Correct 733 ms 45120 KB Output is correct
3 Correct 714 ms 45120 KB Output is correct
4 Correct 740 ms 45120 KB Output is correct
5 Correct 725 ms 45120 KB Output is correct
6 Correct 720 ms 45120 KB Output is correct
7 Correct 706 ms 45120 KB Output is correct
8 Correct 697 ms 45120 KB Output is correct
9 Correct 733 ms 45120 KB Output is correct
10 Correct 853 ms 45120 KB Output is correct
11 Correct 300 ms 45120 KB Output is correct
12 Correct 773 ms 45120 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 45120 KB Output is correct
2 Correct 13 ms 45120 KB Output is correct
3 Correct 12 ms 45120 KB Output is correct
4 Correct 89 ms 45120 KB Output is correct
5 Correct 63 ms 45120 KB Output is correct
6 Correct 17 ms 45120 KB Output is correct
7 Correct 15 ms 45120 KB Output is correct
8 Correct 16 ms 45120 KB Output is correct
9 Correct 13 ms 45120 KB Output is correct
10 Correct 46 ms 45120 KB Output is correct
11 Correct 12 ms 45120 KB Output is correct
12 Correct 11 ms 45120 KB Output is correct
13 Correct 12 ms 45120 KB Output is correct
14 Correct 14 ms 45120 KB Output is correct
15 Correct 13 ms 45120 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 825 ms 33236 KB Output is correct
2 Correct 812 ms 35080 KB Output is correct
3 Correct 725 ms 35080 KB Output is correct
4 Correct 867 ms 35080 KB Output is correct
5 Correct 771 ms 35080 KB Output is correct
6 Correct 793 ms 35080 KB Output is correct
7 Correct 800 ms 35796 KB Output is correct
8 Correct 824 ms 36000 KB Output is correct
9 Correct 837 ms 36000 KB Output is correct
10 Correct 740 ms 37872 KB Output is correct
11 Correct 315 ms 37872 KB Output is correct
12 Correct 783 ms 45120 KB Output is correct
13 Correct 791 ms 45120 KB Output is correct
14 Correct 733 ms 45120 KB Output is correct
15 Correct 714 ms 45120 KB Output is correct
16 Correct 740 ms 45120 KB Output is correct
17 Correct 725 ms 45120 KB Output is correct
18 Correct 720 ms 45120 KB Output is correct
19 Correct 706 ms 45120 KB Output is correct
20 Correct 697 ms 45120 KB Output is correct
21 Correct 733 ms 45120 KB Output is correct
22 Correct 853 ms 45120 KB Output is correct
23 Correct 300 ms 45120 KB Output is correct
24 Correct 773 ms 45120 KB Output is correct
25 Correct 49 ms 45120 KB Output is correct
26 Correct 13 ms 45120 KB Output is correct
27 Correct 12 ms 45120 KB Output is correct
28 Correct 89 ms 45120 KB Output is correct
29 Correct 63 ms 45120 KB Output is correct
30 Correct 17 ms 45120 KB Output is correct
31 Correct 15 ms 45120 KB Output is correct
32 Correct 16 ms 45120 KB Output is correct
33 Correct 13 ms 45120 KB Output is correct
34 Correct 46 ms 45120 KB Output is correct
35 Correct 12 ms 45120 KB Output is correct
36 Correct 11 ms 45120 KB Output is correct
37 Correct 12 ms 45120 KB Output is correct
38 Correct 14 ms 45120 KB Output is correct
39 Correct 13 ms 45120 KB Output is correct
40 Correct 702 ms 48088 KB Output is correct
41 Correct 745 ms 52768 KB Output is correct
42 Correct 791 ms 56868 KB Output is correct
43 Correct 298 ms 56868 KB Output is correct
44 Correct 325 ms 56868 KB Output is correct
45 Correct 803 ms 64852 KB Output is correct
46 Correct 745 ms 67784 KB Output is correct
47 Correct 803 ms 71804 KB Output is correct
48 Correct 416 ms 71804 KB Output is correct
49 Correct 770 ms 76752 KB Output is correct
50 Correct 757 ms 80256 KB Output is correct
51 Correct 756 ms 83920 KB Output is correct