POJ 2472 106 miles to Chicago

問題

無向グラフの情報が与えられる。始点から終点まで辺のコストをかけ合わせたものがパスのコストになる。コストを最大化せよ。

やりかた

辺のコストにlogをかければコストの積を和に変換できる。あとはただの最小経路問題。

以下ソース。

//ダイクストラのコードは略
int main(int argc, char **argv){
  int V, E;
  while(scanf("%d", &V), V){
    scanf("%d", &E);
    g.clear();
    g.resize(V);
    for(int i = 0; i < E; i++){
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      add_edge(a - 1, b - 1, -log(c / 100.0));
    }
    double d = -dijkstra(g, 0, V - 1);
    printf("%.6f percent\n", 100 * exp(d));
  }
}