CODE FESTIVAL 2014 あさプロMiddle : A - 身体バランス

ここらへんはまだ楽ね。
http://code-festival-2014-morning-middle.contest.atcoder.jp/tasks/code_festival_morning_easy_c

問題

N個の町とM個の道路があり、各道路の距離が与えられる。
町sから町tに移動する際、町uを経由して移動したい。
この際、町s→uの最短距離とu→tの最短距離を一致させたい。
そのような町uがあれば答えよ。

解法

町sを始点とする場合と町tを始点とする場合で２通りダイクストラ法を行い、最短距離が一致する町を求めればよい。

int N,M;
int S,T;
vector<pair<int,int> > E[1001];
int dist[2][1001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>S>>T;
	if(S==T) return _P("%d\n",S);
	
	S--,T--;
	FOR(i,M) {
		cin>>x>>y>>r;
		x--,y--;
		E[x].push_back(make_pair(r,y));
		E[y].push_back(make_pair(r,x));
	}
	
	FOR(i,N) dist[0][i]=dist[1][i]=1<<30;
	priority_queue<pair<int,int> > Q;
	dist[0][S]=dist[1][T]=0;
	Q.push(make_pair(0,S));
	Q.push(make_pair(0,10000+T));

	while(Q.size()) {
		pair<int,int> p=Q.top();
		Q.pop();
		int type=p.second/10000;
		int cur=p.second%10000;
		if(p.first != -dist[type][cur]) continue;
		
		FOR(i,E[cur].size()) {
			int tar=E[cur][i].second;
			if(dist[type][tar] > E[cur][i].first + dist[type][cur]) {
				dist[type][tar] = E[cur][i].first + dist[type][cur];
				Q.push(make_pair(-dist[type][tar],type*10000+tar));
			}
		}
	}
	FOR(i,N) if(dist[0][i]==dist[1][i] && dist[0][i]<1<<30) return _P("%d\n",i+1);
	_P("-1\n");
}

まとめ

このあたりは寝起きでも行ける。