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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

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

Q&A

解決済

1回答

1473閲覧

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

l_h_l_h

総合スコア22

C

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

0グッド

0クリップ

投稿2017/10/07 13:53

編集2017/10/07 14:29

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を貰えませんでした
配列の中身などを全部表示するなどして確かめてみたのですが、狙い通りに動いている様に思えますし、自分でいくつか町と経路表を作って動かしてみても、ちゃんと最短経路が結果として表示されました
何時間も悩んでいて困っています
拙いコードと説明文で申し訳ありませんが、どなたかご助力願います

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

LouiS0616

2017/10/07 13:57

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

2017/10/07 14:30

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

回答1

0

自己解決

今更ですが、どうやら制約的に初期化の部分がおかしかったようです

投稿2019/04/14 06:44

l_h_l_h

総合スコア22

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問