AOJ 2371 TransfarTrain

問題

n個の路線がある。
i番目の路線はai個の駅をつなぎ、
それぞれの駅名および、j番目とj+1番目の駅の所要時間が与えられる。

今sの駅からtの駅へ、路線を使っていきたい。
電車はどちらの向きにも使うことができるが、乗り換えには1回あたりTの時間がかかる。
かかる最小の時間を求めよ。
同じ時間で複数の行き方がある場合、最小の乗り換え回数のものを求めよ。
かかる最小の時間および、そのときの乗り換え回数を出力せよ。

制約条件

n≦50000
Σai≦100000
t≦1000

方針

今いる駅, どの路線を使ったかを状態にしてDijkstra.
ただし、同じ駅で何度も乗り換える枝を見ると、計算量がO(E^2)になってTLEするので、
一度乗り換えた駅では2度乗り換えないようにする。
と通る。（furaさんの解法）

A*, SPFAを試してみたが、TLEだった。

ソースコード

int n, t;
string a, b;
map<string, int> id;
vi rail[50000], cost[50000];
vector<pi> pos[100000];
bool trans[100000]; //respect fra2

inline int get(const string &s){
	if(id.count(s)) return id[s];
	int n = id.size();
	return id[s] = n;
}
int main(){
	cin >> n >> t >> a >> b;
	int st = get(a), gl = get(b);
	rep(i, n){
		int k, l;
		cin >> k;
		rep(j, k){
			string s;
			cin >> s;
			l = get(s);
			rail[i].pb(l);
			pos[l].pb(mp(i, j));
		}
		rep(j, k - 1){
			cin >> l;
			cost[i].pb(l);
		}
	}
	set<pi> s;
	priority_queue<pair<pi, pi> > q;
	rep(i, pos[st].size()) q.push(mp(mp(0, 0), pos[st][i]));
	while(!q.empty()){
		pi cur = q.top().S, co = q.top().F;
		int cid = rail[cur.F][cur.S]; q.pop();
		if(s.count(cur)) continue;
		s.insert(cur);
		
		if(cid == gl){
			cout << -co.F << " " << -co.S << endl;
			return 0;
		}
		if(!trans[cid]){
			trans[cid] = 1;
			rep(i, pos[cid].size()) rep(d, 2){
				pi nxt = pos[cid][i], nco = co;
				nxt.S += d ? 1 : -1;
				if(nxt.S < 0 || nxt.S >= rail[nxt.F].size() || s.count(nxt)) continue;
				if(pos[cid][i] == cur) continue;
				nco.S--;
				nco.F -= t + cost[nxt.F][nxt.S - d];
				q.push(mp(nco, nxt));
			}
		}
		rep(d, 2){
			pi nxt = cur, nco = co;
			nxt.S += d ? 1 : -1;
			if(nxt.S < 0 || nxt.S >= rail[nxt.F].size() || s.count(nxt)) continue;
			nco.F -= cost[nxt.F][nxt.S - d];
			q.push(mp(nco, nxt));
		}
	}
	cout << -1 << endl;
	return 0;
}