Submission #833525

#	Time	Username	Problem	Language	Result	Execution time	Memory
833525		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2079 ms	56440 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 100000;
const ll INF = 1e9*MAXN+7;

vector<pair<ll,ll>> adj[MAXN+7];
vector<ll> trace[MAXN+7];
vector<ll> zero(MAXN+7);
map<pair<ll,ll>,ll> zero_edge;

ll uuu,vvv,nnn;
ll ans=INF;

void dijkstra2(){
	ll n=nnn;
	ll s=uuu;
	ll t=vvv;
	
	vector<ll> d(n+7, INF);
	vector<ll> p(n+7, -1);

    d[s] = 0;
    using pii = pair<ll, ll>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    
    
    while (!q.empty()) {
        ll v = q.top().second;
        ll d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

        for (auto edge : adj[v]) {
            ll to = edge.first;
            ll len = edge.second;
			if(zero_edge[{v,to}]==1){
				len=0;
			}
			
            if (d[v] + len < d[to]) {
            	
                d[to] = d[v] + len;
                p[to] = v;
                q.push({d[to], to});
                
            }
        }
    }	
	ans=min(ans,d[t]);
	return;
}

vector<ll> path;

void dfs(ll s,ll v){
	if(v==s){
//		for(auto k : path){
//			cout<<k<<" ";
//		}cout<<"\n";	
		dijkstra2();
		return;
	}
	for(auto k : trace[v]){
		if(zero[k]==1)continue;
		path.push_back(v);
		zero[k]=1;
		
		zero_edge[{v,k}]=1;
		zero_edge[{k,v}]=1;
		
		dfs(s,k);
		
		path.pop_back();
		zero[k]=0;
		zero_edge[{v,k}]=0;
		zero_edge[{k,v}]=0;
	}
	return;
}


void dijkstra1(ll n, ll s, ll t){
	vector<ll> d(n+7, INF);
	vector<ll> p(n+7, -1);

    d[s] = 0;
    using pii = pair<ll, ll>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    
    while (!q.empty()) {
        ll v = q.top().second;
        ll d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

        for (auto edge : adj[v]) {
            ll to = edge.first;
            ll len = edge.second;

            if (d[v] + len < d[to]) {
            	
                d[to] = d[v] + len;
                p[to] = v;
                q.push({d[to], to});
                
                trace[to].clear();
                trace[to].push_back(v);
                
            }else if(d[v]+len == d[to]){
            	trace[to].push_back(v);
			}
        }
    }
	return;
}

int main(){
	ll n,m,s,t,u,v;
	cin>>n>>m;
	cin>>s>>t;
	cin>>u>>v;
	
	for(ll i=0; i<m; i++){
		ll a,b,w;
		cin>>a>>b>>w;
		adj[b].push_back({a,w});
		adj[a].push_back({b,w});
	}
	
	uuu=u;
	vvv=v;
	nnn=n;
	
	dijkstra1(n, s, t);
	dfs(s, t);
	
	cout<<ans<<"\n";
	return 0;
}

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