UVa-10986 : Sending email
問題概要
ノード数V(<20000)、辺数E(<50000)の無向グラフが与えられる。ある点からある点への最短路を求める問題。
解法
acceptされたコード
計算量O(E*log E)。
#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; }