質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.60%

  • C++

    3337questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • プログラミング言語

    669questions

    プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

  • デバッグ

    95questions

    デバッグはプログラムのバグや欠陥を検知し、開発中のバグを取り除く為のプロセスを指します。

【競技プログラミング】WAで反例がわからなくて困っています。

解決済

回答 1

投稿

  • 評価
  • クリップ 1
  • VIEW 831

musharna000

score 12

AOJ0224 Bicycle Dietをダイクストラ法を用いて解いたのですが、
AOJのジャッジではWAが返ってきてしまいます。
いくつか変更を加えてみたり、他の方の解答を見てみたりしたのですが、
なぜACしないのかがどうしても分からず、質問をしている次第です。

私の書いたコードは下記のとおりです。
反例がわかりましたら、コメント頂ければ幸いです。
拙いコードではありますが、宜しくお願い致します。
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <set>
#include <math.h>
#include <utility>
#include <stack>
#include <string.h>
#include <complex>
using namespace std;

const int INF = 1<<29;
const double EPS = 1e-8;
typedef vector<int> vec;
typedef pair<int,int> P;

struct edge{int to,cost;};

struct State{
    int d,m,n;
    bool operator<( const State& right ) const {
        return d > right.d;
    }
};

int d[1<<6][108];
int cake[6];
int m,n,k,di;

int str2index(string& str){
    if(str[0]=='H'){
        return 0;
    }else if(str[0]=='D'){
        return 1;
    }else if(str[0]=='C'){
        return (int)(str[1]-'1'+2);
    }else{
        return (int)(str[1]-'1'+2+m);
    }
}

int main(){
    while(1){
        scanf("%d%d%d%d",&m,&n,&k,&di);
        if(!n)break;

        vector<vector<edge> > g(n+m+2);
        for(int i=0;i<m;i++){
            scanf("%d",&cake[i]);
        }
        for(int i=0;i<di;i++){
            string a,b;
            int c;
            cin >> a >> b >> c;
            int a_i = str2index(a), b_i = str2index(b);
            g[a_i].push_back((edge){b_i,c});
            g[b_i].push_back((edge){a_i,c});
        }

        for(int i=0;i<(1<<m);i++){
            for(int j=0;j<n+m+2;j++){
                d[i][j] = INF;
            }
        }


        d[(1<<m)-1][0] = 0;
        priority_queue<State> que;
        que.push((State){0,(1<<m)-1,0});

        while(que.size()){
            State p = que.top(); que.pop();
            //printf("p.d=%d p.m=%d p.n=%d\n",p.d,p.m,p.n);
            if(d[p.m][p.n] < p.d) continue;
            for(int i=0;i<g[p.n].size();i++){
                int next_d = p.d+g[p.n][i].cost*k;
                if(2<=g[p.n][i].to&&g[p.n][i].to<m+2){
                    int m_i = g[p.n][i].to - 2;
                    if((p.m>>m_i)&1){
                        next_d -= cake[m_i];
                        int next_m = p.m^(1<<m_i);
                        if(next_d < d[next_m][g[p.n][i].to]){
                            d[next_m][g[p.n][i].to] = next_d;
                            que.push((State){next_d,next_m,g[p.n][i].to});
                        }
                    }
                }else{
                    if(next_d < d[p.m][g[p.n][i].to]){
                        d[p.m][g[p.n][i].to] = next_d;
                        que.push((State){next_d,p.m,g[p.n][i].to});
                    }
                }
            }
        }

        int ans = INF;
        for(int i=(1<<m)-1;i>=0;i--) ans = min(ans, d[i][1]);
        cout << ans << endl;
    }

    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+2

str2index関数の中が間違っています。
これでは「L1」と「L10」を渡した結果が同じになってしまいます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/17 12:46

    その通りですね!ご指摘ありがとうございます!
    str2indexを2桁以上にも対応できるように変更したところACされました!
    解法かその実装が間違っているのだと思い込んでmainの中しか見ていませんでした。
    ありがとうございました。とても助かりました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.60%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    C言語 動的メモリ確保とリスト(構造体)を利用したプログラム

    現在このような結果で表示されるプログラムの作成を試みています。 >0p↲ >p >1d↲ >pd >0i↲ >ipd >2a↲ >ipad というように、格納位置

  • 解決済

    C言語 式の構文エラー 内容について

    複数の単語からなる文を入力し,各単語の先頭文字を大文字に変えて表示させる というプログラムを作っているのですが、コンパイル時に ------ Borland C++ 5.5.1 f

  • 解決済

    皆様のお答えを聞かせてください。打ちこんだ整数を逆に並べて出力する

    このコードはマイナスの値を打つと、アラームが鳴り整数値を打つように 指示します。そして整数値が打ちこまれると、それを10で割り余りを出す、10で割るという繰り返しで引っくり返した数

  • 解決済

    【C言語】スタックをリストで実現するプログラム

    毎度お世話になっております。 高橋麻奈さんの「やさしいC アルゴリズム」をみて勉強しているのですが、リストを使ったスタックのコードで、がコンパイルエラーになってしまいました。 コ

  • 解決済

    出入力c++

    入出力のコードを書いていたのですが、エラーがでてしまいます。 問題点を指摘してくださるとうれしいです。 コード /*  * stream.cpp  *  *  Created on

  • 解決済

    C言語 キューの問題の解答が分かりません。

    C言語の勉強をやり始めて二か月の者です。 今、キューの問題を解いているのですが、解答が分かりません。この問題の解説はあるのですが、読んでも理解するのが難しくコードが書けません。

  • 解決済

    for文 scanf など全般

    前提・実現したいこと ここに質問したいことを詳細に書いてください (例)PHP(CakePHP)で●●なシステムを作っています。   ■■な機能を実装中に以下のエラーメッセー

  • 解決済

    AOJ ITP1_3_C の問題がうまくいきません。

    AOJ(会津オンラインジャッジ)を最近始めて勉強しています。 ITP1_3_C 二つの数の交換  の問題でうまくいきません。 入力は3000行以内で、整数x,yを用いて

同じタグがついた質問を見る

  • C++

    3337questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • プログラミング言語

    669questions

    プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

  • デバッグ

    95questions

    デバッグはプログラムのバグや欠陥を検知し、開発中のバグを取り除く為のプロセスを指します。