

[F - ヘビの JOI
君](https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_f)に挑戦したのですがTLEになります。  
しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。

[code]

    int N, M,X,T[10000];
    
    struct edge{
        int to,cost;
    };
    
    struct situ {
        int cost,v,dist,type;
    
        bool operator<(const situ& rhs) const
        {
            return cost < rhs.cost;
        }
    };
    
    vector<edge>G[10005];
    
    int d[10005][205][3];
    
    void dijkstra(int s) {
    
        d[0][0][0] = 0;
        priority_queue<situ> que;
        que.push({ 0, s, 0,0 });
        while (!que.empty()) {
            situ p = que.top(); que.pop();
            int cost = p.cost, v = p.v;
            if (d[v][p.dist][p.type] < cost)continue;
            for (edge u : G[v]) {
    
                if (abs(p.type - T[u.to]) > 1 && p.dist+u.cost < X) {
                    continue;
                }
                int type = p.type,dist = min(p.dist + u.cost,X);
                if (T[u.to] != 1) {
                    type = T[u.to];
                    dist = 0;
                }
    
                if (d[u.to][dist][type] > d[v][p.dist][p.type] + u.cost) {
                    d[u.to][dist][type] = d[v][p.dist][p.type] + u.cost;
                    que.push({ d[u.to][dist][type],u.to,dist,type });
    
                }
            }
        }
    }
    int main()
    {
        cin >> N >> M >> X;
        rep(i, N) {
            cin >> T[i];
        }
        rep(i, M) {
            int a, b,d;
            cin >> a >> b >> d;
            a--; b--;
            G[a].push_back({ b,d });
            G[b].push_back({ a,d });
        }
        rep(i, N) {
            rep(j, X + 1) {
                fill_n(d[i][j], 3, INF);
            }
        }
        dijkstra(0);
        N--;
        int ans = INF;
        rep(i, X+1) {
            rep(j, 3) {
                ans = min(ans, d[N][i][j]);
            }
        }
        cout << ans << endl;
    
    }
    
[/code]

次にサンプルコード

[code]

    #include<cstdio>
    #include<vector>
    #include<utility>
    #include<queue>
    
    using namespace std;
    
    const int MAX_N = 10000;
    const int MAX_X = 200;
    
    const int inf = 1e9;
        struct Edge{
            int to, cost;
            Edge(){}
            Edge(int to, int cost):to(to), cost(cost){}
        };
    
        vector<Edge> G[MAX_N];
        int color[MAX_N]; //temperature (0/1/2)
    
        int N, X;
    
        int dis[MAX_N][2][MAX_X + 1];
    
        typedef pair<int, int> P; //<temperature of the nearest non-comfortable room (0 or 2), distance from there>
        typedef pair<int, P> P2; //<vertex, P>
        typedef pair<int, P2> P3; //<distance from s, P2>
    
        P update_state(P p, Edge e){
            if(color[e.to] == 0){
                if(p.first == 2 && p.second + e.cost < X){
                    return P(-1, -1);
                }else{
                    return P(0, 0);
                }
            }else if(color[e.to] == 1){
                int d = min(X, p.second + e.cost);
                return P(p.first, d);
            }else{
                if(p.first == 0 && p.second + e.cost < X){
                    return P(-1, -1);
                }else{
                    return P(2, 0);
                }
            }
        }
    
        void dijkstra(){
            priority_queue<P3, vector<P3>, greater<P3> > que;
            for(int i = 0; i < N; ++i){
                for(int j = 0; j < 3; ++j){
                    for(int k = 0; k < MAX_X + 1; ++k){
                        dis[i][j][k] = inf;
                    }
                }
            }
    
            dis[0][0][0] = 0;
            que.push(P3(0, P2(0, P(0, 0))));
    
            while(!que.empty()){
                P3 p3 = que.top();
                que.pop();
                int d = p3.first;
                int v = p3.second.first;
                P prv_state = p3.second.second;
                if(dis[v][prv_state.first / 2][prv_state.second] < d) continue;
                for(int i = 0; i < G[v].size(); ++i){
                    P np = update_state(prv_state, G[v][i]);
                    if(np == P(-1, -1)) continue;
                    int nd = d + G[v][i].cost;
                    int nv = G[v][i].to;
                    if(dis[nv][np.first / 2][np.second] <= nd) continue;
                    dis[nv][np.first / 2][np.second] = nd;
                    que.push(P3(nd, P2(nv, np)));
                }
            }
        }
    
        int solve(){
            dijkstra();
            int ans = inf;
            for(int c = 0; c < 2; ++c){
                for(int d = 0; d <= X; ++d){
                    ans = min(ans, dis[N - 1][c][d]);
                }
            }
            for(int v = 0; v < N; ++v){
                int tmp = inf;
                for(int c = 0; c < 2; ++c){
                    for(int d = 0; d <= X; ++d){
                        tmp = min(tmp, dis[v][c][d]);
                    }
                }
            }
            return ans;
        }
    
        void input(){
            int M;
            scanf("%d%d%d", &N, &M, &X);
            for(int i = 0; i < N; ++i){
                scanf("%d", color + i);
            }
            for(int i = 0; i < M; ++i){
                int u, v, d;
                scanf("%d%d%d", &u, &v, &d);
                u--;
                v--;
                G[u].push_back(Edge(v, d));
                G[v].push_back(Edge(u, d));
            }
        }
    
        int main(){
            input();
            int ans = solve();
            printf("%d\n", ans);
            return 0;
        }
    
[/code]

ちなみにサンプルコードは最悪でも実行時間60msです。  
制約などは最初のURLに載っています。  
追記：  
自分のコードの省略した部分です

[code]

    #define _USE_MATH_DEFINES
    #include<math.h>
    
    //#include<cmath>
    
    #include<deque>
    #include<queue>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<cmath>
    #include<tuple>
    #include<string>
    #include<chrono>
    #include<functional>
    #include<iterator>
    #include<random>
    #include<unordered_set>
    #include<array>
    #include<map>
    #include<iomanip>
    #include<assert.h>
    #include<bitset>
    #include<stack>
    #include<memory>
    
    
    
    //#include "Ants.h"
    using namespace std;
    typedef long long ll;
    #define rad_to_deg(rad) (((rad)/2/M_PI)*360)
    #define EPS (1e-7)
    #define INF (1e9)
    #define PI (acos(-1))
    #define rep(i,n) for(int i=0;i<n;i++)
    #define show(s) cout<<s<<endl
    #define chmin(x,y) x=min(x,y)
    #define chmax(x,y) x=max(x,y)
    #define LINF (1000000000000000000ll)
    typedef pair<int, int> P;
    
[/code]


CC BY-SA 4.0
2019-12-07T06:00:57.170
61199
2021-07-06T12:00:50.140
2019-12-07T08:00:17.903
4236
24617
question
c++ アルゴリズム
なぜこのコードは非効率なのか？


問題の解説サイトを読みましたか？  
<https://www.ioi-
jp.org/joi/2016/2017-yo/2017-yo-t6/review/2017-yo-t6-review.html>

まず、質問者のプログラムは ダイクストラ法になっていません。  
while 分で取り出した１つの部屋について すべての訪問可能な部屋の情報を調べて計算し  
少しでも効率がいい経路を queue に入れていますが、再帰的にすべてのルートを計算しているのとそれほど変わりがありません。

まず、ダイクストラ法を使って計算するロジックを書く練習をしてください。  
ダイクストラ法では、次の部屋へ到達する最短距離は、前の部屋への最短距離を保持した配列から  
計算することで無駄な計算を行わないというアルゴリズムです。


CC BY-SA 4.0
2019-12-07T07:05:19.940
61202
2019-12-07T07:13:41.530
2019-12-07T07:13:41.530
18851
18851
61199
answer


質問者ですが原因が分かったので報告致します。結論からいうと恐らくコード本体(ダイクストラとmain関数部分)には問題はありません。しかし、struct
situのoperator<の符号の向きが逆だったようです。ほかにも細かな変更を加えたので一応コードを載せておきます。

[code]

    #define _USE_MATH_DEFINES
    #include<math.h>
    
    //#include<cmath>
    
    #include<deque>
    #include<queue>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<cmath>
    #include<tuple>
    #include<string>
    #include<chrono>
    #include<functional>
    #include<iterator>
    #include<random>
    #include<unordered_set>
    #include<array>
    #include<map>
    #include<iomanip>
    #include<assert.h>
    #include<bitset>
    #include<stack>
    #include<memory>
    
    
    
    //#include "Ants.h"
    using namespace std;
    typedef long long ll;
    #define rad_to_deg(rad) (((rad)/2/M_PI)*360)
    #define EPS (1e-7)
    #define INF (1e9)
    #define PI (acos(-1))
    #define rep(i,n) for(int i=0;i<n;i++)
    #define show(s) cout<<s<<endl
    #define chmin(x,y) x=min(x,y)
    #define chmax(x,y) x=max(x,y)
    #define LINF (1000000000000000000ll)
    typedef pair<int, int> P;
    
    int N, M,X,T[10000];
    
    struct edge{
        int to,cost;
    };
    
    struct situ {
        int cost,v,dist,type;
    
        bool operator<(const situ& rhs) const
        {
            if (cost == rhs.cost) {
                return dist < rhs.dist;
            }
            return cost > rhs.cost;
        }
    };
    
    vector<edge>G[10005];
    
    int d[10005][205][3];
    
    void dijkstra(int s) {
    
        priority_queue<situ> que;
        que.push({ 0, s, 0,0 });
        while (!que.empty()) {
            situ p = que.top(); que.pop();
            int cost = p.cost, v = p.v;
            if (d[v][p.dist][p.type] < cost)continue;
    
            //cout <<cost<<" "<< v <<" "<<p.type<<" "<<p.dist<< endl;
            //cout << que.top().cost << endl;
            for (edge u : G[v]) {
    
                if (abs(p.type - T[u.to]) > 1 && p.dist+u.cost < X) {
                    continue;
                }
                int type = p.type,dist = min(p.dist + u.cost,X);
                if (T[u.to] != 1) {
                    type = T[u.to];
                    dist = 0;
                }
    
                if (d[u.to][dist][type] > d[v][p.dist][p.type] + u.cost) {
                    d[u.to][dist][type] = d[v][p.dist][p.type] + u.cost;
                    for (int x = dist; x >= 0; --x) {
                        d[u.to][x][type] = min(d[u.to][x][type],d[u.to][dist][type]);
                    }
                    que.push({ d[u.to][dist][type],u.to,dist,type });
    
                }
            }
        }
    }
    int main()
    {
        cin >> N >> M >> X;
        rep(i, N) {
            cin >> T[i];
        }
        rep(i, M) {
            int a, b,d;
            cin >> a >> b >> d;
            a--; b--;
            G[a].push_back({ b,d });
            G[b].push_back({ a,d });
        }
        rep(i, N) {
            rep(j, X + 1) {
                fill_n(d[i+1][j], 3, INF);
            }
        }
        dijkstra(0);
        N--;
        int ans = INF;
        rep(i, X+1) {
            rep(j, 3) {
                ans = min(ans, d[N][i][j]);
            }
        }
        cout << ans << endl;
    
    }
    
[/code]

本題は解決したのですが、一つ疑問があります。operator< の符号の向きです。  
確かsort関数を同じようにstructで昇順にソート{sort(begin,end,cmp)}とするために関数cmpを作っていたのですが、このときの符号の向きは'<'だったと記憶しております。なぜ'>'となるのでしょうか。教えていただけると助かります。  
追記：最悪実行時間は53msでした。サンプルとほぼ同じのようです。


CC BY-SA 4.0
2019-12-07T08:26:50.100
61206
2019-12-07T08:26:50.100
24617
61199
answer