UVa-10985 : Rings'n'Ropes

問題概要

ノード数V(<120)の無向グラフがある。2点を選んで、その最短路のいずれかに含まれる辺の数を数える。2点をうまく選んでその数の最大値を求める問題。

解法

まずWarshall-Floydで最短路を求めておく。次に2点を固定する。各辺e=(v,u)に対して、d(start, v) + 1 + d(u, goal) = d(start, goal)ならそれは最短路に含まれると言える。これを利用して数え上げるだけ。

acceptされたコード

計算量O(V^4)でちょっと怪しい。

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAX_N = 20000;
const int INF = 1<<29;

struct edge{
	int target, cost;
	edge(int target_, int cost_):target(target_), cost(cost_){}
};

vector<edge> graph[MAX_N];
int dist[MAX_N];
int N, M, S, T;

struct state{
	int cost, cur;
	state(int cost_, int cur_):cost(cost_), cur(cur_){}
};

bool operator<(const state& lhs, const state& rhs){
	return lhs.cost > rhs.cost;
}

void init(){
	for(int i=0; i<MAX_N; i++){
		graph[i].clear();
	}
	fill(dist, dist+MAX_N, INF);

	scanf("%d%d%d%d",&N, &M, &S, &T);
	for(int i=0; i<M; i++){
		int from, tar, cost;
		scanf("%d%d%d", &from, &tar, &cost);
		graph[from].push_back(edge(tar, cost));
		graph[tar].push_back(edge(from, cost));
	}
}

void solve(){
	priority_queue<state> que;
	que.push( state(0, S) );
	dist[S] = 0;

	while(!que.empty()){
		state tp = que.top(); que.pop();
		int cur = tp.cur, cost = tp.cost;
		if(cost > dist[cur]){
			continue;
		}

		for(int i=0; i<(int)graph[cur].size(); i++){
			int v = graph[cur][i].target, nd = cost + graph[cur][i].cost;
			if(nd < dist[v]){
				dist[v] = nd;
				que.push(state(nd, v));
			}
		}
	}

	if(dist[T]==INF){
		puts("unreachable");
	}
	else{
		printf("%d\n", dist[T]);
	}
}

int main(){
	int T;
	scanf("%d",&T);
	for(int c=1; c<=T; c++){
		init();
		printf("Case #%d: ", c);
		solve();
	}

	return 0;
}