Submission #1315615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315615		jokuk	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	200 ms	23556 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
int main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,r,s,t,start,stop;
	cin>>n;
	cin>>r;
	cin>>s;
	cin>>t;
	cin>>start;
	cin>>stop;
	vector<vector<pair<int,long long int>>> adj(n+1);
	for(int i=0;i<r;i++)
	{
		int u,v;
		long long int w;
		cin>>u;
		cin>>v;
		cin>>w;
	    adj[u].push_back({v,w});
	    adj[v].push_back({u,w});
	}
	priority_queue<pair<long long int ,int>> q;
	long long int distx[n+1],disty[n+1];
	for(int i=1;i<=n;i++)
	{
		distx[i]=LLONG_MAX;
	}
	distx[start]=disty[stop]=0;
	q.emplace(0,start);
		while(!q.empty())
		{
			  auto [w, u] = q.top();
	    	q.pop();
	    	w=-w;
	    	if(distx[u]!=w)
	    	{
	    		continue;
			}
	    	 for (auto [v,ww] : adj[u])
	    	{
	             if (distx[v]>ww+w)
	             {
	             	 q.emplace(-(distx[v]=ww+w),v);
				 }
	        }
		}
	q.emplace(0,stop);
		while(!q.empty())
		{
			auto [w, u] = q.top();
	    	q.pop();
	    	w=-w;
	    	if(disty[u]!=w)
	    	{
	    		continue;
			}
	    	 for (auto [v, ww] : adj[u])
	    	{
	             if (disty[v]>ww+w)
	             {
	             	 q.emplace(-(disty[v]=ww+w),v);
				 }
	        }
		}
	priority_queue<tuple<long long int,long long int,long long int,long long int,int>> q1;// reminder  dist, minx+miny, minx, miny, u
	pair<long long int,long long int> dist[n+1];
	for (int i = 1; i <= n; i++) 
	{
	  	dist[i] = make_pair(LLONG_MAX, LLONG_MAX); 
	}
	dist[s]=make_pair(0,distx[s]+disty[s]);
	q1.emplace(0,-(distx[s]+disty[s]),-distx[s],-disty[s],s);
	while(!q1.empty())
	{
		auto [w, sum, minx, miny, u] = q1.top();
    	q1.pop();
    	w=-w;
    	sum=-sum;
    	minx=-minx;
    	miny=-miny;
    	if(make_pair(w,sum)!=dist[u])
    	{
    		continue;
		}
    	 for (auto [v, ww] : adj[u])
    	{
         	long long int nw = w+ww, nx=min(minx,distx[v]),ny=min(miny,disty[v]),ns=nx+ny;
      		if (dist[v].first>nw) 
	  		q1.emplace(-(dist[v].first = nw),-(dist[v].second=ns),-nx,-ny,v);
        	else if (dist[v].first == nw && dist[v].second > ns) 
			q1.emplace(-(dist[v].first = nw), -(dist[v].second = ns), -nx, -ny, v);
		}
    }
        cout<<min(dist[t].second,distx[stop])<<"\n";
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45