Submission #708868

#	Time	Username	Problem	Language	Result	Execution time	Memory
708868		myrcella	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	334 ms	35584 KiB

commuter_pass

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e5+10;

int n,m,s,t,U,V;
vector <pii> edge[maxn];
ll dis[4][maxn];
pq <pll,vector<pll>,greater<pll> > q;
ll ans[maxn][2][2];

void dijkstra(int sta,int id) {
	memset(dis[id],inf,sizeof(dis[id]));
	dis[id][sta]=0;
	q.push({0,sta});
	while (!q.empty()) {
		ll u = q.top().se,d=q.top().fi;
		q.pop();
		if (dis[id][u]!=d) continue;
		for (pii v:edge[u]) {
			if (dis[id][v.fi]>d+v.se) {
				dis[id][v.fi]=d+v.se;
				q.push({d+v.se,v.fi});
			}
		}
	}
}

ll getdp(int u,int flag1,int flag2) {
	if (u==t) return flag1*dis[2][u]+flag2*dis[3][u];
	if (ans[u][flag1][flag2]!=-1) return ans[u][flag1][flag2];
	ll ret = 1e16;
	for (pii v:edge[u]) {
		if (dis[1][v.fi]+v.se+dis[0][u]!=dis[0][t]) continue;
		ret=min(ret,getdp(v.fi,flag1,flag2));
		if (flag1==1) ret=min(ret,getdp(v.fi,0,flag2)+dis[2][u]);
		if (flag2==1) ret=min(ret,getdp(v.fi,flag1,0)+dis[3][u]);
	}
	return ans[u][flag1][flag2]=ret;
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	memset(ans,-1,sizeof(ans));
	cin>>n>>m>>s>>t>>U>>V;
	rep(i,0,m) {
		int u,v,w;
		cin>>u>>v>>w;
		edge[u].pb({v,w});
		edge[v].pb({u,w});
	}
	dijkstra(U,2);
	dijkstra(s,0);
	dijkstra(t,1);
	dijkstra(V,3);
//	debug(dis[2][V]);
	cout<<min(dis[2][V],getdp(s,1,1));
	return 0;
}

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