Submission #618651

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <functional>
#include <map>

using namespace std;

//  E[i]: vertexes which can be reased from i
//  W[i]: their weight
template<class T>
vector<T> dijkstra(vector<vector<int>> E, vector<vector<T>> W, int s, T inf)
{
    int n = (int)E.size();
    
    vector<T> D(n, inf);
    typedef pair<T,int> P;
    priority_queue<P,vector<P>,greater<P>> Q;
    
    D[s] = T();
    Q.push(make_pair(D[s], s));

    while (!Q.empty())
    {
        int d = Q.top().first;
        int p = Q.top().second;
        Q.pop();
        if (d > D[p])
            continue;
        for (int i=0; i<(int)E[p].size(); i++)
        {
            int t = E[p][i];
            if (d+W[p][i] < D[t])
                D[t] = d+W[p][i],
                Q.push(make_pair(D[t], t));
        }
    }
    return D;
}

int main()
{
	int N, M, src, dst;
	cin>>N>>M>>src>>dst;
	vector<int> L(M);
	vector<vector<int>> s(M);
	vector<vector<int>> w(M);
	for (int i=0; i<M; i++)
	{
		cin>>L[i];
		s[i] = vector<int>(L[i]);
		for (int j=0; j<L[i]; j++)
			cin>>s[i][j];
		w[i] = vector<int>(L[i]-1);
		for (int j=0; j<L[i]-1; j++)
			cin>>w[i][j];
	}

	vector<vector<int>> E(N);
	vector<vector<int>> W(N);
	for (int i=0; i<M; i++)
	for (int j=0; j<L[i]-1; j++)
	{
		E[s[i][j]].push_back(s[i][j+1]);
		W[s[i][j]].push_back(w[i][j]);
		E[s[i][j+1]].push_back(s[i][j]);
		W[s[i][j+1]].push_back(w[i][j]);
	}

	int inf = 0x40000000;
	vector<int> D2 = dijkstra(E, W, dst, inf);

	vector<vector<pair<int, int>>> V(N);
	for (int i=0; i<M; i++)
	for (int j=0; j<L[i]; j++)
		V[s[i][j]].push_back(make_pair(i, j));

	vector<vector<int>> w0(M), w1(M);
    for (int i=0; i<M; i++)
    {
        w0[i] = w1[i] = vector<int>(L[i]);
        w0[i][0] = 0;
        for (int j=1; j<L[i]; j++)
            w0[i][j] = w0[i][j-1] + w[i][j-1];
        w1[i][L[i]-1] = 0;
        for (int j=L[i]-2; j>=0; j--)
            w1[i][j] = w1[i][j+1] + w[i][j];
    }

	auto solve = [&](int limit)
	{
		vector<int> D1(N, inf);
		typedef pair<int, int> P;
		priority_queue<P,vector<P>,greater<P>> Q;
		D1[src] = 0;
		Q.push(make_pair(0, src));

		while (!Q.empty())
		{
			int d = Q.top().first;
			int p = Q.top().second;
			Q.pop();
			if (d > D1[p])
				continue;
			for (int i=0; i<(int)V[p].size(); i++)
			{
				int a = V[p][i].first;
				int b = V[p][i].second;

				if (0<b &&
					d+w0[a][b]+D2[s[a][0]]<=limit)
				{
					int t = s[a][b-1];
					if (d+w[a][b-1]<D1[t])
						D1[t] = d+w[a][b-1],
						Q.push(make_pair(D1[t], t));
				}
				if (b<L[a]-1 &&
					d+w1[a][b]+D2[s[a][L[a]-1]]<=limit)
				{
					int t = s[a][b+1];
					if (d+w[a][b]<D1[t])
						D1[t] = d+w[a][b],
						Q.push(make_pair(D1[t], t));
				}
			}
		}

		return D1[dst]<=limit;
	};

	int ans = 0;
	for (int b=inf; b>0; b/=2)
		if (!solve(ans+b))
			ans += b;
	cout<<ans+1<<endl;
}

Submission Info

Judge Result