oj.uz

Submission #45183

# Submission time Handle Problem Language Result Execution time Memory
45183 2018-04-11T17:15:03 Z Pajaraja Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 949 ms 35952 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())
	{
		int t=-pq.top().first,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:39: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:58: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:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<k[ord[i]].size();j++)
               ~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:98: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:68: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:73: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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 33508 KB Output is correct
2 Correct 755 ms 35196 KB Output is correct
3 Correct 810 ms 35196 KB Output is correct
4 Correct 860 ms 35196 KB Output is correct
5 Correct 833 ms 35196 KB Output is correct
6 Correct 885 ms 35196 KB Output is correct
7 Correct 842 ms 35672 KB Output is correct
8 Correct 829 ms 35952 KB Output is correct
9 Incorrect 921 ms 35952 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 35952 KB Output is correct
2 Correct 714 ms 35952 KB Output is correct
3 Correct 810 ms 35952 KB Output is correct
4 Correct 806 ms 35952 KB Output is correct
5 Correct 949 ms 35952 KB Output is correct
6 Correct 783 ms 35952 KB Output is correct
7 Correct 865 ms 35952 KB Output is correct
8 Correct 821 ms 35952 KB Output is correct
9 Correct 742 ms 35952 KB Output is correct
10 Correct 757 ms 35952 KB Output is correct
11 Correct 305 ms 35952 KB Output is correct
12 Correct 813 ms 35952 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 35952 KB Output is correct
2 Correct 12 ms 35952 KB Output is correct
3 Correct 12 ms 35952 KB Output is correct
4 Correct 86 ms 35952 KB Output is correct
5 Correct 53 ms 35952 KB Output is correct
6 Correct 18 ms 35952 KB Output is correct
7 Correct 15 ms 35952 KB Output is correct
8 Correct 17 ms 35952 KB Output is correct
9 Correct 18 ms 35952 KB Output is correct
10 Correct 51 ms 35952 KB Output is correct
11 Correct 12 ms 35952 KB Output is correct
12 Incorrect 13 ms 35952 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 33508 KB Output is correct
2 Correct 755 ms 35196 KB Output is correct
3 Correct 810 ms 35196 KB Output is correct
4 Correct 860 ms 35196 KB Output is correct
5 Correct 833 ms 35196 KB Output is correct
6 Correct 885 ms 35196 KB Output is correct
7 Correct 842 ms 35672 KB Output is correct
8 Correct 829 ms 35952 KB Output is correct
9 Incorrect 921 ms 35952 KB Output isn't correct
10 Halted 0 ms 0 KB -