Submission #616861

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll inf=1e11;
typedef pair<int,ll> P;
struct edge{
	int to,mis;
	ll c,mc;
	edge(int a,int b,ll c,ll d) :to(a),mis(b),c(c),mc(d){}
};
vector<edge> G[25252];
int N,M,s,t;
int tmp[25252],tc[25252];
ll d0[25252],d[25252];
void dijkstra(ll T){
	rep(i,N) d[i]=inf;
	d[s]=0;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,s));
	while(!que.empty()){
		P p=que.top();que.pop();
		int v=p.sc;
		if(d[v]<p.fs) continue;
		for(edge e:G[v]) if(d[v]+e.mc+d0[e.mis]<=T){
			if(d[e.to]>d[v]+e.c){
				d[e.to]=d[v]+e.c;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}
int main(){
	cin>>N>>M>>s>>t;
	rep(i,M){
		int L;
		cin>>L;
		rep(i,L) cin>>tmp[i];
		rep(i,L-1) cin>>tc[i];
		ll sum=0;
		for(int i=L-2;i>=0;i--){
			sum+=tc[i];
			G[tmp[i]].pb(edge(tmp[i+1],tmp[L-1],tc[i],sum));
		}
		sum=0;
		for(int i=1;i<=L-1;i++){
			sum+=tc[i-1];
			G[tmp[i]].pb(edge(tmp[i-1],tmp[0],tc[i-1],sum));
		}
	}
	rep(i,N) d0[i]=inf;
	d0[t]=0;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,t));
	while(!que.empty()){
		P p=que.top();
		que.pop();
		int v=p.sc;
		if(d0[v]<p.fs) continue;
		for(edge e:G[v]){
			if(d0[e.to]>d0[v]+e.c){
				d0[e.to]=d0[v]+e.c;
				que.push(P(d0[e.to],e.to));
			}
		}
	}
	ll ub=1e10,lb=0;
	while(ub-lb>1){
		ll T=(ub+lb)/2;
		dijkstra(T);
		if(d[t]<=T) ub=T;
		else lb=T;
	}
	cout<<ub<<endl;
}

Submission Info

Judge Result