제출 #1003035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003035		tamir1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	264 ms	43608 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n,m,s,t,u,v,x,y,z,i,dis[100001],ans=1e18;
vector<pair<ll,ll>> g[100001];
priority_queue<pair<ll,ll>> q;
map<pair<ll,ll>,bool> mp;
void ko(){
	q.push({0,u});
	memset(dis,-1,sizeof dis);
	while(!q.empty()){
		z=q.top().ff;
		x=q.top().ss;
		q.pop();
		if(dis[x]!=-1) continue;
		dis[x]=-z;
		for(pair<ll,ll> i:g[x]){
			if(dis[i.ff]==-1){
				if(mp[{x,i.ff}]) q.push({z,i.ff});
				else q.push({z-i.ss,i.ff});
			}
		}
	}
	ans=min(ans,dis[v]);
}
void dfs(ll x){
	if(x==s){
		ko();
		return;
	}
	for(pair<ll,ll> i:g[x]){
		if(dis[x]==dis[i.ff]+i.ss){
			mp[{x,i.ff}]=1;
			mp[{i.ff,x}]=1;
			dfs(i.ff);
			mp[{x,i.ff}]=0;
			mp[{i.ff,x}]=0;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m >> s >> t >> u >> v;
	for(i=1;i<=m;i++){
		cin >> x >> y >> z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	memset(dis,-1,sizeof dis);
	q.push({0,s});
	while(!q.empty()){
		z=q.top().ff;
		x=q.top().ss;
		q.pop();
		if(dis[x]!=-1) continue;
		dis[x]=-z;
		for(pair<ll,ll> i:g[x]){
			if(dis[i.ff]==-1) q.push({z-i.ss,i.ff});
		}
	}
	dfs(t);
	cout << ans;
}

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