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