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; }