-1

F - ヘビの JOI 君に挑戦したのですがTLEになります。
しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。

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;

}

次にサンプルコード

#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;
    }

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

#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;
3
  • 前の質問 にあったincludeやdefineが、どちらのソースも不足していてコンパイルできないようです。修正してみてください。
    – kunif
    Commented 2019年12月7日 6:58
  • 追加しましたが、こういうものは省略したほうがよいのではないでしょうか?
    – Ranger
    Commented 2019年12月7日 7:56
  • 4
    有っても無くてもよいなら削ってもよいですが、無いと検証できないものまで削っては駄目でしょう。この場合、サンプルコードは回答例へのリンクでも良かったかもしれません。
    – kunif
    Commented 2019年12月7日 7:59

2 件の回答 2

0

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

#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;

}

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

1
-2

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

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

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

2
  • ダイクストラ法はpriority_queueをつかっても実現できるのではないでしょうか?一応ある状態での最短距離が確定している辺はcontinueするロジックにしたつもりですが、どこか問題があるのでしょうか。
    – Ranger
    Commented 2019年12月7日 7:52
  • 私のほうが知識が古かったようですね。 最短経路を保持する配列と 次の値を決定するための配列を別々に持って実装する C 言語で実装したときの知識で判断していました。 nw.tsuda.ac.jp/lec/dijkstra で 疎結合なグラフで利用する「順位優先探索」という方法なんですね。 失礼しました。
    – user18851
    Commented 2019年12月7日 11:25

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。