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

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

ただいまの
回答率

90.51%

  • C

    3689questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Atcoder ABC073 問題Dが分からないです

受付中

回答 0

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 229

l_h_l_h

score 7

Atcoderのコンテストより、どうしても解けない問題があったので質問させていただきます

http://abc073.contest.atcoder.jp/tasks/abc073_d

問題は此方です

自分の組んだプログラムは以下の通りです(一部、ウェブで検索して見つけたアルゴリズムをコピペしてそのまま流用しています)

#include<stdio.h>
#define ERROR -1

void fl(int M,int dp[M][M]);

int next_perm(int *p, int n)
{
  int i, j, k, tmp;
  /* 上位桁のほうが下位桁よりも小さいところまで移動 */
  for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
  /* pが最大(次の並べ替えがない) */
  if(i == 0) return 0;
  /* p[i-1]より値の大きい最も下位の桁をp[j]とする */
  for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
  /* p[i-1]とp[j]とを交換 */
  tmp = p[i-1], p[i-1] = p[j], p[j] = tmp;
  /* p[i]から最下位までを逆順 */
  for(k = 0; k <= ((n-1)-i)/2; k++)
    tmp = p[i+k], p[i+k] = p[(n-1)-k], p[(n-1)-k] = tmp;
  return 1;
}

int main(){
    int N,M,R;//N=街の数 M=道の数 R=訪れる街の数
    int i,j;//ループ用変数
    scanf("%d %d %d",&N,&M,&R);
    if(N<2||N>200)return ERROR;
    if(M<1||M>N*(N-1)/2)return ERROR;
    if(R<2||R>8||R>N)return ERROR;
    int res=0,res_tmp[100001],R_ka=1;
    int R_num[R];
    int dist[M];//キョリ
    int d[N][N];//どこからどこへ?のキョリ格納用
    int a,b,tmp;//一時変数

    for(i=1;i<N+1;i++){
        for(j=1;j<N+1;j++){
            d[i][j]=100001;
        }
    }

    if(N<R)return ERROR;
    for(i=0;i<R;i++){
        scanf("%d ",&R_num[i]);
    }
    for(i=0;i<M;i++){
        scanf("%d %d %d",&a,&b,&dist[i]);
        if(a==b||a==0||b==0||dist==0)return ERROR;
        d[a][b]=dist[i];//ex:a=1,b=2,dist=2→d[1][2]=2
    }
    for(i=1;i<N+1;i++){
        for(j=1;j<N+1;j++){
            if(d[i][j]!=100001&&d[j][i]==100001){
                d[j][i]=d[i][j];
            }
            else if(d[i][j]!=100001&&d[j][i]!=100001){
                if(d[i][j]>d[j][i]){
                    d[i][j]=d[j][i];
                }else{
                    d[j][i]=d[i][j];
                }
            }
        }
    }

    fl(N,d);
    for(i=1;i<N+1;i++){
        for(j=1;j<N+1;j++){
            if(d[i][j]==100001){
                d[i][j]=-1;
            }
            if(i==j){
                d[i][i]=-1;
            }
        }
    }

    for(i=R;i!=1;i--){
        R_ka=i*R_ka;
    }
    int cnt=0;
    for(j=0;j<R_ka;){
          /* 並べ替え */
          do {
              res=0;
              for(i=0;i<R-1;i++){
                  res+=d[R_num[i]][R_num[i+1]];

              }

               res_tmp[j]=res;
               j++;
               cnt++;
               if(cnt==R_ka)break;
          } while(next_perm(R_num, R));

    }

    res=100001;
    for(i=0;i<R_ka;i++){
        if(res>res_tmp[i]){
            res=res_tmp[i];
        }
    }

    printf("%d\n",res);
    return 0;
}

void fl(int M,int dp[M][M]){
    int i,j,k;
    for (k = 1; k < M+1; k++) {
      for (j = 1; j < M+1; j++) {
          for(i=1;i<M+1;i++){
            if (dp[i][j] > dp[i][k] + dp[k][j]){
              dp[i][j] = dp[i][k] + dp[k][j];
            }
        }
      }
    }
}

挙動としては、まず町間の距離を最大値(100001)で初期化し、その後入力した距離を代入、そこからワーシャルフロイド法(void fl関数)を用いて上書きしていっています
最短経路の順番を求めるために、配列R_numを並び替える必要があるため、next_permにより全通り並び替えています
変数R_kaは訪れる町の数の階乗で、この回数だけ配列を並び替えていきます
配列res_tmpに、計算した経路の重みを順に代入していき、最後にその中から一番小さいものをres(これが答えになります)に代入しています
途中で何度か出現するfor文は、配列dの中身を弄っています
初めに配列dの中身を全部を100001で初期化しましたが、経路入力後、d[1][1](町1から町1への距離)などのあり得ない部分には-1を代入、また経路が存在していない部分(d[i][j]が100001から上書きされていない場所)にも-1を代入しています
このプログラムを動かしてみたところ、一部の問題しかACを貰えませんでした
配列の中身などを全部表示するなどして確かめてみたのですが、狙い通りに動いている様に思えますし、自分でいくつか町と経路表を作って動かしてみても、ちゃんと最短経路が結果として表示されました
何時間も悩んでいて困っています
拙いコードと説明文で申し訳ありませんが、どなたかご助力願います

  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正の依頼

  • LouiS0616

    2017/10/07 22:57

    二か所編集してください。第一は、コードを見やすく表示する、マークダウン表記です。編集画面を開き、コードを選択した状態で<code>ボタンを押してください。第二は、リンクの貼り付けです。[説明文](URL)のように書くか、編集画面のURL/リンクボタン(地球のマーク)を押してリンクを挿入してください。

    キャンセル

  • l_h_l_h

    2017/10/07 23:30

    失礼いたしました 修正させていただきました

    キャンセル

まだ回答がついていません

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

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

関連した質問

  • 解決済

    linux 処理時間の表示

    C言語でLinuxを使っています。メモリを確保したりするプログラムなのですが、以下のプログラムを修正して 、5秒間で何回の入れ替えを行えるかを計測できるようにしてもらいたいです。初

  • 解決済

    fgetsを使った文字列の分割

    前提・実現したいこと AOJ 1_5Aの問題で、よくないとされるscanf以外を使用した解決を図りたいです。 問題内容は、 トランプの枚数が足りないので現在持っているカードを入

  • 解決済

    C言語の線型散策(逐次散策)

    C言語の線型散策(逐次散策)の質問です。 以下の演習がうまく行きません。 ご教授ください。 【要素数nの配列v内のkeyと等しい全要素の添字を配列idxに格納する関数searc

  • 解決済

    [c]一つのデータでカラム数が変わるデータの読み込み

    質問失礼します。プログラム初心者です。 以下のような〜〜〜.datを fp1 = fopen(fname1,"r"); while((ret = fscanf(fp1,"%d %d

  • 解決済

    [初心者]golangの関数の戻り値について

    環境 golang1.8.3 IDE: gogland わからないこと golangの勉強をしようと、fizzbuzzなるものをやってみようと思いまして、コーディングしたのです

  • 解決済

    c言語で10進数が格納された配列を文字(char)に変換する関数の作成

    前提・実現したいこと c言語で10進数が格納された配列を文字(char)に変換する関数を作りたい 発生している問題・エラーメッセージ 変換がされないとの、putchar((in

  • 受付中

    リスト構造と待ち行列

    リスト構造と待ち行列をしたいのですが、よくわかりません。 おすすめのサイトや説明おねがいします。 #include <stdio.h> #include <stdlib.h>

  • 解決済

    c言語 入門レベル問題

    a,b 入力したら、b、a 逆の順番に出てたいです、 下記プログラミング7,8入力したら、a = 0, b = 7 出てしまいました。 不備なところ教えていただけますか。 #i

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

  • C

    3689questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。