Submission #2009314

---

Source Code Expand

#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef pair<lint,int>pli;
typedef pair<pii,pii>piipii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

const int DEBUG=0;


const int M=200000;
const int N=30000;
int n,m,src,dst;
vi s[M];
vector<lint> w[M];

vector<piipii> g[N];

void debug_vi(const vi&v){
  if(DEBUG){
    rep(i,v.size())cerr<<" "<<v[i];
    cerr<<endl;
  }
}

vector<lint> solve(int s){
  vector<lint> ret(n,1.e16);
  priority_queue<pli,vector<pli>,greater<pli> > que;
  que.push(pii(0,s));
  while(!que.empty()){
    pii t=que.top();que.pop();
    int v=t.second;
    lint d=t.first;
    if(ret[v]<=d)continue;
    ret[v]=d;
    for(auto w:g[v]){
      int wv=w.first.first;
      int wc=w.first.second;
      que.push(pli(d+wc,wv));
    }
  }
  return ret;
}

vector<lint> solve_delay(int s, const vector<lint> &sdis){
  vector<lint> ret(n,1e16);
  priority_queue<pli,vector<pli>,greater<pli> > que;
  que.push(pli(0,s));
  while(!que.empty()){
    pii t=que.top();que.pop();
    int v=t.second;
    lint d=t.first;
    if(ret[v]<=d)continue;
    ret[v]=d;
    for(auto w:g[v]){
      int wv=w.first.first;
      int wc=w.first.second;
      pii lane=w.second;
      int nv=lane.first;
      int nc=lane.second;
      que.push(pli(max(d+wc,nc+sdis[nv]),wv));
    }
  }
  return ret;
}

int main(){
  cin>>n>>m>>src>>dst;
  rep(i,m){
    int l;
    cin>>l;
    s[i]=vi(l),w[i]=vector<lint>(l-1);
    rep(j,l)cin>>s[i][j];
    rep(j,l-1)cin>>w[i][j];
    vi wacc(l);
    rep(j,l-1)wacc[j+1]=wacc[j]+w[i][j];
    rep(j,l-1){
      int u=s[i][j];
      int v=s[i][j+1];
      g[v].push_back(piipii(pii(u,w[i][j]),pii(s[i][l-1],wacc[l-1]-wacc[j])));
      g[u].push_back(piipii(pii(v,w[i][j]),pii(s[i][0],wacc[j])));
    }
  }
  vector<lint> vdst=solve(dst);
  vector<lint> ans=solve_delay(dst,vdst);
  cout<<ans[src]<<endl;
}

Submission Info

Judge Result