Submission #834445

#	Time	Username	Problem	Language	Result	Execution time	Memory
834445		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	271 ms	39528 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define piii pair<long long ,long long>
const ll nmax =2e5+5;
const ll mod=1e9+7;
ll distu[nmax],distv[nmax],a,b,c,dists1[nmax],dists2[nmax],dists[nmax],distt[nmax],distt1[nmax],distt2[nmax],maxx;
int n,m;
vector<piii> edge[nmax],rev[nmax];
priority_queue<piii,vector<piii>,greater<piii>> q;
void dijkstra(ll u)
{
    memset(distu,0x3f, sizeof(distu));
	distu[u]=0;
	priority_queue<piii, vector<piii> , greater<piii>> Q ;
	Q.push({0,u});
	while(!Q.empty()){
		piii top = Q.top();
		Q.pop();
		ll u = top.second;
		ll kc = top.first;
		if(kc > distu[u]) continue;
		for(auto it: edge[u])
		{
			ll v = it.first;
			ll w = it.second;
			if(distu[v]>distu[u]+w)
			{
				distu[v]=distu[u] + w ;
				Q.push({distu[v],v});
			}
		}

	}
}
void dijkstra2(ll u)
{
    memset(distv,0x3f, sizeof(distv));
	distv[u]=0;
	priority_queue<piii, vector<piii> , greater<piii>> Q ;
	Q.push({0,u});
	while(!Q.empty()){
		piii top = Q.top();
		Q.pop();
		ll u = top.second;
		ll kc = top.first;
		if(kc > distv[u]) continue;
		for(auto it: edge[u])
		{
			ll v = it.first;
			ll w = it.second;
			if(distv[v]>distv[u]+w)
			{
				distv[v]=distv[u] + w ;
				Q.push({distv[v],v});
			}
		}

	}
}
void dijkstra3(ll u)
{
    memset(dists,0x3f, sizeof(dists));
    memset(dists1,0x3f, sizeof(dists1));
    memset(dists2,0x3f, sizeof(dists2));
	dists[u]=0;
	dists1[u]=distu[u];
	dists2[u]=distv[u];
	priority_queue<piii, vector<piii> , greater<piii>> Q ;
	Q.push({0,u});
	while(!Q.empty()){
		piii top = Q.top();
		Q.pop();
		ll u = top.second;
		ll kc = top.first;
		if(kc > dists[u]) continue;
		for(auto it: edge[u])
		{
			ll v = it.first;
			ll w = it.second;
			if(dists[v]>dists[u]+w)
			{
				dists[v]=dists[u]+w;
				dists1[v]=min(dists1[u],distu[v]);
				dists2[v]=min(dists2[u],distv[v]);
				Q.push({dists[v],v});
			}
			else if (dists[v]==dists[u]+w)
            {
                dists1[v]=min(dists1[u],dists1[v]);
				dists2[v]=min(dists2[u],dists2[v]);
            }
		}

	}
}
void dijkstra4(ll u)
{
    memset(distt,0x3f, sizeof(distt));
    memset(distt1,0x3f, sizeof(distt1));
    memset(distt2,0x3f, sizeof(distt2));
	distt[u]=0;
	distt1[u]=distu[u];
	distt2[u]=distv[u];
	priority_queue<piii, vector<piii> , greater<piii>> Q ;
	Q.push({0,u});
	while(!Q.empty()){
		piii top = Q.top();
		Q.pop();
		ll u = top.second;
		ll kc = top.first;
		if(kc > distt[u]) continue;
		for(auto it: edge[u])
		{
			ll v = it.first;
			ll w = it.second;
			if(distt[v]>distt[u]+w)
			{
				distt[v]=distt[u]+w;
				distt1[v]=min(distt1[u],distu[v]);
				distt2[v]=min(distt2[u],distv[v]);
				Q.push({distt[v],v});
			}
			else if (distt[v]==distt[u]+w)
            {
                distt1[v]=min(distt1[u],distt1[v]);
				distt2[v]=min(distt2[u],distt2[v]);
            }
		}

	}
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int u,v,s,t;
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for (ll i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        edge[a].push_back({b,c});
        edge[b].push_back({a,c});
    }
    dijkstra(u);
    dijkstra2(v);
    dijkstra3(s);
    dijkstra4(t);
    maxx=distu[v];
    for (int i=1;i<=n;++i)
        if (dists[i]+distt[i]==dists[t])
            maxx=min({maxx,dists1[i]+distt2[i],dists2[i]+distt1[i]});
    cout<<maxx;
}

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