Submission #617166

---

Source Code Expand

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

typedef long long Int;
typedef pair<Int, Int> P;
typedef pair<P, Int> T;
#define INF (1LL << 60)
vector<P> edge[32400];
vector<T> sedge[32400];
vector<Int> w[324000];
vector<Int> s[324000];

Int n, m, src, dst;
Int l[32400];
Int tmp;
Int dists[324000], distd[32400];
Int up[324000], down[324000];                      

void dijkstra(Int s, Int *dist){
	fill(dist, dist + 32400, INF);	
	priority_queue<P, vector<P>, greater<P> > pq;
	
	dist[s] = 0;
	pq.push(P(0, s));
	
	while(!pq.empty()){
		P tmp = pq.top();pq.pop();
		Int d = tmp.first;
		Int from = tmp.second;
		if(dist[from] < d)continue;
		for(Int i = 0;i < edge[from].size();i++){
			Int to = edge[from][i].first;
			Int dis = edge[from][i].second;
			if(dist[to] > dist[from] + dis){
				dist[to] = dist[from] + dis;
				pq.push(P(dist[to], to));
			}
		}
	}
}



void maxdijkstra(Int s, Int *dist){
	fill(dist, dist + 32400, INF);
	
	priority_queue<P, vector<P>, greater<P> > pq;
	
	dist[s] = 0;
	pq.push(P(0, s));
	
	while(!pq.empty()){
		P tmp = pq.top();pq.pop();
		Int d = tmp.first;
		Int from = tmp.second;
		if(dist[from] < d)continue;
		for(Int i = 0;i < sedge[from].size();i++){
			Int to = sedge[from][i].first.first;
			Int dis = sedge[from][i].first.second;
			Int ww = sedge[from][i].second;
			if(dist[to] > max(dist[from] + ww, dis)){
				dist[to] = max(dist[from] + ww, dis);
				pq.push(P(dist[to], to));
			}
		}
	}
}

int main(){
	cin >> n >> m >> src >> dst;
	for(Int i = 0;i < m;i++){
		cin >> l[i];
		for(Int j = 0;j < l[i];j++){
			cin >> tmp;
			s[i].push_back(tmp);
		}
		for(Int j = 0;j < l[i] - 1;j++){
			cin >> tmp;
			w[i].push_back(tmp);
			edge[s[i][j]].push_back(P(s[i][j+1], tmp));
			edge[s[i][j+1]].push_back(P(s[i][j], tmp));
		}
	}
	                     
	dijkstra(src, dists);
	dijkstra(dst, distd);
	
//	for(int i = 0;i < n;i++)cout << dists[i] << " " << distd[i] << endl;
	
	for(Int i = 0;i < m;i++){
		up[0] = down[l[i]-1] = 0;
		for(Int j = 0;j < l[i]-1;j++){
			up[j+1] = w[i][j];
			down[j] = w[i][j];
		}
		Int upper = s[i][l[i]-1];
		Int lower = s[i][0];
		for(Int j = 1;j < l[i];j++)up[j] += up[j-1];//, cout << j << " " << up[j] << endl;
		for(Int j = l[i]-2;j >= 0;j--)down[j] += down[j+1];//, cout << j << " " << down[j] << endl;
		for(Int j = 0;j < l[i]-1;j++){
			Int a = s[i][j], b = s[i][j+1];
//			cout << a << " " << b << " " << down[j] << " " << distd[upper] << endl;
//			cout << b << " " << a << " " << up[j+1] << " " << distd[lower] << endl;
			sedge[b].push_back(T(P(a, down[j] + distd[upper]), w[i][j]));
			sedge[a].push_back(T(P(b, up[j+1] + distd[lower]), w[i][j]));
		}
	}
	
	maxdijkstra(dst, dists);
	
	cout << dists[src] << endl;	
	return 0;
}

Submission Info

Judge Result