AtCoder ARC #061 : E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

典型テクのはずなのに妙に手間取った。
http://arc061.contest.atcoder.jp/tasks/arc061_c

問題

1～NのN個の駅からなる鉄道網がある。
２駅間を結ぶ線路がM個あり、各線路iは駅P[i]とQ[i]を結ぶ。
また、その線路は会社C[i]によって運営されている。

同じ会社が運営する線路を利用する場合、連続して線路何本移動しても料金は1である。
この鉄道網に対し、駅1から駅Nに移動する場合の料金の最小値を求めよ。

解法

同じ会社の路線だけで連結する駅同士は、互いにコスト1で移動できる。
かといってこれらの駅を直接双方向に結ぶと、辺の数が多くなりすぎる。

そこで、駅からなるグラフを考える際、別途会社に相当する頂点を加え、その駅と会社の間にコスト１の辺を張ろう。
すると、辺の数は元の線路数の倍に抑え、題意に合うグラフを作れる。

あとはこのグラフで最短経路を求め、２で割れば解。

int N,M;
vector<pair<int,int>> EE[1010101];
int did[101010];
vector<int> TE[101010];

vector<int> E[301010];
int id=100001;
int dist[303030];

void dfs(int cur,int x) {
	if(did[cur]==x) return;
	did[cur]=x;
	E[id].push_back(cur);
	E[cur].push_back(id);
	FORR(r,TE[cur]) dfs(r,x);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		EE[r].push_back({x,y});
	}
	MINUS(did);
	FOR(i,1010100) if(EE[i].size()) {
		vector<int> V;
		FORR(e,EE[i]) {
			TE[e.first].push_back(e.second);
			TE[e.second].push_back(e.first);
			V.push_back(e.first);
			V.push_back(e.second);
		}
		
		FORR(r,V) if(did[r]!=i) {
			dfs(r,i);
			id++;
		}
		FORR(e,EE[i]) {
			TE[e.first].clear();
			TE[e.second].clear();
		}
	}
	
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;
	queue<int> Q;
	Q.push(1);
	while(Q.size()) {
		x = Q.front();
		Q.pop();
		FORR(e,E[x]) {
			if(dist[e]>dist[x]+1) {
				dist[e]=dist[x]+1;
				Q.push(e);
			}
		}
	}
	
	if(dist[N]>0x3f0000) dist[N]=-1;
	else dist[N]/=2;
	cout<<dist[N]<<endl;
	
	
}

まとめ

本番はもっと無駄の多い解法を取ってしまった。