Submission #45185

#	Time	Username	Problem	Language	Result	Execution time	Memory
45185		Pajaraja	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	867 ms	83920 KiB

commuter_pass

#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 (stderr)

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 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45