初歩的なグラフの問題 (ID:72936)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文 とりあえずコードを書いたほうがいいとのことでしたので、自分で考えた方法でコードを実装してみました。 まだコンパイルが通っただけで未テストです。 同じ地点を2度と通らないという条件で全2地点間を最短で結ぶコストを求めてみました。 まだプログラマとしては初心者レベルなのでコードがうまくいっているかどうかわからない状態です。 #include<stdio.h> const int size=100;//グラフの最大サイズ、適当な値 const int max=1000000000; const int memoSize=(size-1)/32+1; int g[size][size];//グラフ int rootMemo[size][size][memoSize];//グラフ間の2地点をつなぐ最大カロリー経路で通る地点を１bit単位で保存 bool connectOK(int k,int i,int j){ //点iとk kとｊを結ぶ最大カロリー経路に重複部分がないかチェック for(int l=0;l<memoSize;l++){ if((rootMemo[i][k][l]&rootMemo[k][j][l])!=0) return false; } return true; } void connect(int k,int i,int j){ for(int l=0;l<memoSize;l++){ rootMemo[i][j][l]=rootMemo[i][k][l]|rootMemo[k][j][l]; } rootMemo[i][j][k/32]|=(k%32); } void wf(int m){ //拡張ワーシャルフロイド法 int t; for(int k=0;k<m;k++){ for(int i=0;i<m;i++){ if(g[i][k]==max)continue; for(int j=0;j<m;j++){ if(g[k][j]==max)continue; t=g[i][k]+g[k][j]; if(t<g[i][j] && connectOK(k,i,j)){ connect(k,i,j); } } } } } int main() { int n,m;//nはノードの数、ｍは点の数,点は０からｍ−１まで番号をつける scanf("%d %d",&n,&m); for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ g[i][j]=max; for(int k=0;k<memoSize;k++){ rootMemo[i][j][k]=0;//経路の初期化 } } } int a,b,c; for(int i=0;i<n;i++){ scanf("%d %d %d",&a,&b,&c);//ノードの重み、道路で消費するカロリー。 g[a][b]=g[b][a]=c; } for(int i=0;i<m;i++){ scanf("%d",&c);//点で得られる重み、店舗で摂取できるカロリー for(int j=0;j<m;j++){ if(g[j][i]!=max)g[j][i]-=c; } g[i][i]=max; } wf(m); //ここの時点で同じ地点を2度と通らず結んだ最短経路が配列ｇに出力されているはず }