なぜこのコードは非効率なのか？


[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]




質問者ですが原因が分かったので報告致します。結論からいうと恐らくコード本体(ダイクストラと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でした。サンプルとほぼ同じのようです。

