POJ 2686 spfa+dp
3055 ワード
标题:mの都市があって、今一人でaからbまで歩いて、都市の間にp本の無方向の辺があって、すべての辺はすべて権力の値があって、今この人はn枚の切符があって、1枚の切符は1つの馬の数量があって、この人は1本の辺を歩くたびに1枚の切符を使って、1枚の切符は1回しか使えなくて、x->yから仮定して、距離はzで、彼は1枚の切符を使って、馬の数量はlで、ではx->yからかかる時間はz/lです.
A->bから一番短い時間はいくらですか.
この問題のデータ量は非常に小さく,n=8,m=30であれば,切符の使用状況を直接状圧で表すことができることに注目できる.直接SPFA,dis配列は2次元を開き,1次元は現在の状態を記録する.
そして、次の状態を列挙するたびに.
最後に答えを更新すればいいです.
A->bから一番短い時間はいくらですか.
この問題のデータ量は非常に小さく,n=8,m=30であれば,切符の使用状況を直接状圧で表すことができることに注目できる.直接SPFA,dis配列は2次元を開き,1次元は現在の状態を記録する.
そして、次の状態を列挙するたびに.
最後に答えを更新すればいいです.
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
using namespace std;
#define N 1 << 10
double dis[33][N] ;
bool vis[33][N] ;
int n , m , p , a , b ;
int v[33] ;
int road[33][33] ;
void init() {
for (int i = 1 ; i <= n ; i ++ )cin >> v[i] ;
for (int i = 0 ; i <= m ; i ++ )for (int j = 0 ; j <= m ; j ++ )road[i][j] = inf ;
while(p -- ) {
int x , y , z ;
scanf("%d%d%d",&x,&y,&z) ;
road[x][y] = road[y][x] = min(road[x][y] , z) ;
}
}
PII qe[N * N] ;
void spfa() {
mem(vis ,0) ;
for (int i = 0 ; i <= m ; i ++ )
for (int j = 0 ; j < 1 << n ; j ++ )
dis[i][j] = inf ;
dis[a][0] = 0 ;
vis[a][0] = 1 ;
int h = 0 , t = 0 ;
qe[h ++ ] = mp(a , 0) ;
while(h > t) {
PII tp = qe[t ++ ] ;
vis[tp.FI][tp.SE] = 0 ;
for (int i = 1 ; i <= m ; i ++ ) {
if(road[tp.FI][i] != inf) {
for (int j = 0 ; j < n ; j ++ ) {
if( ( (1 << j) & tp.SE) == 0) {
int ns = (1 << j) | tp.SE ;
if(dis[i][ns] > dis[tp.FI][tp.SE] + 1.0 * road[tp.FI][i] / v[j + 1]) {
dis[i][ns] = dis[tp.FI][tp.SE] + 1.0 * road[tp.FI][i] / v[j + 1] ;
if(!vis[i][ns]) {
qe[h ++ ] = mp(i , ns) ;
vis[i][ns] = 1 ;
}
}
}
}
}
}
}
}
int main() {
while(cin >> n >> m >> p >> a >> b , (n + m + p + a + b)) {
init() ;
spfa() ;
double ans = inf ;
for (int i = 0 ; i < 1 << n ; i ++ )
ans = min(ans , dis[b][i]) ;
if(ans == inf)puts("Impossible") ;
else printf("%.3f
",ans) ;
// cout << ans << endl;
}
return 0 ;
}