oj.uz

Submission #45155

# Submission time Handle Problem Language Result Execution time Memory
45155 2018-04-11T14:34:18 Z Pajaraja Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 884 ms 108496 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];
bool st[100007];
void djikstra(int s,int a)
{
	priority_queue<pair<long long,int> > pq;
	fill(d[a],d[a]+n+1,-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]+n+1,-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);
	int cur=0;
	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<n;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=n-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: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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 37316 KB Output is correct
2 Correct 789 ms 42560 KB Output is correct
3 Correct 744 ms 44568 KB Output is correct
4 Correct 843 ms 48008 KB Output is correct
5 Correct 792 ms 51800 KB Output is correct
6 Correct 826 ms 55480 KB Output is correct
7 Correct 787 ms 61644 KB Output is correct
8 Correct 884 ms 65244 KB Output is correct
9 Incorrect 805 ms 67368 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 825 ms 71408 KB Output is correct
2 Correct 739 ms 73688 KB Output is correct
3 Correct 803 ms 77380 KB Output is correct
4 Correct 753 ms 80800 KB Output is correct
5 Correct 774 ms 84260 KB Output is correct
6 Correct 756 ms 88808 KB Output is correct
7 Correct 854 ms 92276 KB Output is correct
8 Correct 736 ms 95004 KB Output is correct
9 Correct 725 ms 98376 KB Output is correct
10 Correct 748 ms 102008 KB Output is correct
11 Correct 337 ms 102008 KB Output is correct
12 Correct 754 ms 108496 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 108496 KB Output is correct
2 Correct 10 ms 108496 KB Output is correct
3 Correct 10 ms 108496 KB Output is correct
4 Correct 88 ms 108496 KB Output is correct
5 Correct 50 ms 108496 KB Output is correct
6 Correct 12 ms 108496 KB Output is correct
7 Correct 15 ms 108496 KB Output is correct
8 Correct 15 ms 108496 KB Output is correct
9 Correct 12 ms 108496 KB Output is correct
10 Correct 53 ms 108496 KB Output is correct
11 Correct 11 ms 108496 KB Output is correct
12 Incorrect 12 ms 108496 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 37316 KB Output is correct
2 Correct 789 ms 42560 KB Output is correct
3 Correct 744 ms 44568 KB Output is correct
4 Correct 843 ms 48008 KB Output is correct
5 Correct 792 ms 51800 KB Output is correct
6 Correct 826 ms 55480 KB Output is correct
7 Correct 787 ms 61644 KB Output is correct
8 Correct 884 ms 65244 KB Output is correct
9 Incorrect 805 ms 67368 KB Output isn't correct
10 Halted 0 ms 0 KB -