アルゴリズムのメモ
2009.07.09 22:48 ACM/ICPC 2009
#include #include #include #define rep(i, n) for ( int i = 0; i < n; i++ ) using namespace std; #define MAX 30 #define VMAX 30 #define INFTY (1 << 21) class State{ public: int pos, from, v; double cost; State( int pos=0, int from=0, int v=0, double cost=0): pos(pos), from(from), v(v), cost(cost){} bool operator < ( const State &s) const{ return cost > s.cost; } }; int n, m, s, g, D[MAX+1][MAX+1], C[MAX+1][MAX+1]; void dijkstra(){ priority_queue PQ; double cost[MAX][MAX][VMAX+1]; bool visited[MAX][MAX][VMAX+1]; // pos, from, v rep(i, n) rep(j, n) rep(k, VMAX+1) { cost[i][j][k] = INFTY; visited[i][j][k] = false; } for ( int v = 0; v < n; v++ ){ if ( D[s][v] == INFTY ) continue; cost[v][s][1] = D[s][v]/1.0; PQ.push( State(v, s, 1, D[s][v]/1.0) ); } State u, v; while( !PQ.empty() ){ u = PQ.top(); PQ.pop(); visited[u.pos][u.from][u.v] = true; if ( u.pos == g && u.v == 1 ) { printf("%.12lf\n", cost[u.pos][u.from][u.v] ); return; } for ( int v = 0; v < n; v++ ){ if ( D[u.pos][v] == INFTY ) continue; for ( int nv = u.v-1; nv <= u.v+1; nv++ ){ if ( visited[v][u.pos][nv] || nv > C[u.pos][v] || v == u.from ) continue; double c = cost[u.pos][u.from][u.v] + 1.0*D[u.pos][v]/nv; if ( cost[v][u.pos][nv] > c ){ cost[v][u.pos][nv] = c; PQ.push( State(v, u.pos, nv, c) ); } } } } cout << "unreachable" << endl; } main(){ int x, y, d, c; while( cin >> n >> m && n ){ cin >> s >> g; s--; g--; rep(i, n) rep(j, n) { D[i][j] = C[i][j] = INFTY; } rep(i, m){ cin >> x >> y >> d >> c; x--; y--; D[x][y] = D[y][x] = d; C[x][y] = C[y][x] = c; } dijkstra(); } }
テーマ : プログラミング - ジャンル : コンピュータ
| コメント(0) | トラックバック(0) | ↑ページトップ |
管理人にのみ表示
↑ページトップ
この記事にトラックバックする(FC2ブログユーザー)
Footmark
このブログをリンクに追加する Powered By FC2 ブログ