問題概要

N$ ( N\leq 30)$ノードMエッジの多重辺のない無向グラフ上を移動してスタートノードSからゴールノードGを目指す．SからGに行くまでの最短時間を求めたい．

エッジにはそれぞれ制限速度c$ ( c\leq 30)$と距離d$ ( d\leq 100)$が決まっている．速度は，Sを出発する際は1でなければならず，Gに到着する際にも1でなければならない．また，ノードに到着するたびに速度を1増やす・1減らす・変えないのいずれかを選択できる．

解法概要

初めは(ノード番号)と(そのノードに到達する際の速度)の直積の要素数だけノードを持ったグラフを頑張って作って，前の状態番号を保持するダイクストラでやっていたのだが，テストケース (非サンプルケース) が1つだけ合わない．

結局，先輩の解法を見て，グラフはNノードで，ダイクストラで状態遷移させるときに制限速度を気にするようにしたら通った．

(さすがに雑すぎるので後日加筆します)

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <complex>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

struct State{
    int node, prev, v;
    double t;
    State(int node, int prev, int v, double t): node(node), prev(prev), v(v), t(t) {}
    bool operator>(const State& s) const{
        return t > s.t;
    }
};

struct Edge{
    int to;
    double d;
    int c;
    Edge(int to, double d, int c): to(to), d(d), c(c) {}
};

vector<Edge> G[30];

double dist[30][30][30];
priority_queue<State, vector<State>, greater<State> > que;

void dijkstra(int start){
    fill(dist[0][0], dist[29][30], 1e5);
    dist[start][start][0] = 0.0;
    State start_state = State(start, start, 0, 0.0);
    que.push(start_state);
    
    while(!que.empty()){
        State s = que.top(); que.pop();
        if(dist[s.prev][s.node][s.v] < s.t) continue;
        for(Edge e: G[s.node]){
            if(e.to == s.prev) continue;
            for(int dv=-1;dv<=1;dv++){
                if(s.v+dv <= 0 || e.c < s.v+dv) continue;
                if(dist[s.node][e.to][s.v+dv] > dist[s.prev][s.node][s.v] + e.d/(s.v+dv)){
                    dist[s.node][e.to][s.v+dv] = dist[s.prev][s.node][s.v] + e.d/(s.v+dv);
                    que.push(State(e.to, s.node, s.v+dv, dist[s.node][e.to][s.v+dv]));
                }
            }
        }
    }
}

int main(){
    int n, m, s, g, x, y, c;
    double d;
    while(cin >> n >> m && n){
        for(int i=0;i<30;i++){
            G[i].clear();
        }
        
        cin >> s >> g;
        s--; g--;
        
        for(int i=0;i<m;i++){
            cin >> x >> y >> d >> c;
            x--; y--;
            G[x].push_back(Edge(y, d, c));
            G[y].push_back(Edge(x, d, c));
        }
        
        dijkstra(s);
        double ans = dist[0][g][1];
        for(int i=1;i<n;i++){
            ans = min(ans, dist[i][g][1]);
        }
        if(abs(ans - 1e5) < 1){
            printf("unreachable\n");
            continue;
        }
        printf("%.10lf\n", ans);
    }
}

所感

ICPC国内予選，お互いに頑張りましょう！！

(これが言いたかっただけ)

NoiminのNoise

ICPC国内予選 2009 D - 離散的速度

問題概要

解法概要

ソースコード

所感