Submission #618285

---

Source Code Expand

#include <iostream>
#include <climits>
#include <map>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

#define show(x) cout << #x << "=" << x << endl
#define show2(x,y) cout << #x << "=" << x << "," << #y << "=" << y <<  endl
#define show3(x,y,z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z <<  endl

typedef long long ll;
ll INF = LONG_MAX/2;

struct edge{
    int from,to,trm;
    ll cost,trmc;
    edge(int _from, int _to, ll _cost, int _trm, ll _trmc) {from=_from; to=_to; cost=_cost; trm=_trm; trmc=_trmc;}
};
typedef pair<ll,int> P;

int V;
vector<edge> G[25260];
ll d[25260];
ll c[25260];

void dijkstra(int s){
    
    priority_queue<P,vector<P>,greater<P>> que; 
    fill(d,d+V,INF);
    d[s]=0;
    que.push(P(0,s));
    
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v]<p.first) continue;
        for(int i=0; i<G[v].size();i++){
            edge e = G[v][i];
            if(d[e.from] > d[e.to]+e.cost){
                d[e.from] = d[e.to]+e.cost;
                que.push(P(d[e.from],e.from));
            }
        }
    }
}

void dijkstra2(int s){
    
    priority_queue<P,vector<P>,greater<P>> que; 
    fill(c,c+V,INF);
    memset(c, 0x3f, sizeof c);
    c[s]=0;
    que.push(P(0,s));
    
    ll tmp;
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(c[v]<p.first) continue;
        for(int i=0; i<G[v].size();i++){
            edge e = G[v][i];
            tmp = max(c[e.to]+e.cost, d[e.trm] + e.trmc);
            //show2(d[e.trm] ,e.trmc);
            //show2(c[e.to]+e.cost, d[e.trm] + e.trmc);
            //show(tmp);
            if(c[e.from] > tmp){
                c[e.from] = tmp;
                que.push(P(c[e.from],e.from));
            }
        }
    }
}

int main(){
    
    int N,M,src,dst;
    cin>>N>>M>>src>>dst;
    
    V=N;
    
    int L;
    for(int j=0;j<M;j++){
        cin>>L;
        //cout << L << endl;
        vector<int> s(L);
        vector<ll> W(L);
        for(int i=0;i<L;i++) cin>>s[i]; 
        //for(int j=0;j<L;j++) cout << s[j] << endl;
        for(int i=0;i<L-1;i++) cin>>W[i+1], W[i+1]+=W[i];
        //for(int j=0;j<L;j++) cout << W[j] << endl;
        for(int i=0;i<L-1;i++){
            G[s[i+1]].push_back(edge(s[i], s[i+1], W[i+1]-W[i], s[L-1], W[L-1]-W[i]));
            G[s[i]].push_back(edge(s[i+1], s[i], W[i+1]-W[i], s[0], W[i+1]-W[0]));
            //show3(s[i],s[L-1],W[L-1]-W[i]);
            //show3(s[i+1],s[0],W[i+1]-W[0]);
        }
    }

    dijkstra(dst);
    //for(int i=0;i<N;i++) cout << d[i] << ' '; cout << endl;
    dijkstra2(dst);
    //for(int i=0;i<N;i++) cout << d[i] << ' '; cout << endl;
    //for(int i=0;i<N;i++) cout << c[i] << ' '; cout << endl;
    cout << c[src] << endl;
    return 0;
}

Submission Info

Judge Result